interviewalgo
, , ,
Source
Edit
History

LC206 反转链表

Introduction

Question：LC206 反转链表

Analysis

一道比较常见的简单题。

题目的意思简单来说就是给你一个单链表，然后将他倒置过来。例如，输入为1 -> 2 -> 3，输出为3 -> 2 -> 1。

双指针

用双指针应该很容易解决这个问题。大概就是维护两个指针cur和pre：

  • cur：指向链表当前节点
  • pre：指向链表前一个节点

然后在对链表向前遍历的过程中，不断将cur->next指向pre，即可实现翻转。

这样我们就能在一次遍历中完成反转链表的功能，同时循环中的语句也是一些简单赋值而已，所以

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)

递归算法

一般用递归去思考问题的时候，我们需要先假设我们已经有一个函数实现了对该问题的子问题的求解，然后去思考怎么利用这个函数去实现我们自己的函数。换句话说我们要如何利用一个子问题的解去构造大问题的解。

因此在这里，我们可以先假设已经有一个函数可以将当前节点的下一个节点所代表的链表反转了。也就是说，对于输入1 -> 2 -> 3 -> 4 -> 5，通过调用那个假设的函数，我们得到了5 -> 4 -> 3 -> 2，所以我们只需要将1插入到这个链表的尾部即可。由于是单链表，所以其实我们现在拿到的指针是5，但是要实现尾插的话，我们需要的是2。

  • 简单的想话，可以通过遍历去获取，但是这个时间复杂度就会很高，因为每次递归都需要向前遍历一次的话，相当于是两个循环，也就是O(n^2)的时间复杂度。
  • 再仔细想想的话，可以在递归时维护一个尾指针，但是这样写起来就有点略微繁琐了，特别是在无法返回多个值的编程语言中。
  • 不过这个问题并不需要这么做，因为除了在反转后的链表中存在2之外，在反转前的链表中也同样有这个节点。即我们可以从节点1->next取到2的指针。

由于递归时所做的操作的时间和空间复杂度为O(1)，然后递归深度为O(n)，所以：

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

Implement

双指针

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    if (head == nullptr) return head;
    ListNode *pre = nullptr, *cur = head, *temp;
    while(cur) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

递归算法

1
2
3
4
5
6
7
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode *res = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return res;
}

One More Thing

  • 可以通过循环不变式来证明算法正确性 #ToDo