Grizzly's daily
0%

单链表解题技巧4——反转链表

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

本文是关于单链表的反转问题, 存在反转全部链表和部分区间链表的情况.

涉及 leetcode 的206. 反转链表和92. 反转链表 II.

反转链表

题目1

首先来看题目206. 反转链表: 给你单链表的头节点 head , 请你反转链表, 并返回反转后的链表.

示例1:

输入: head = [1,2,3,4,5]

输出: [5,4,3,2,1]

示例2:

输入: head = []

输出: []

理解一下1

反转很好理解, 链表本来是指向其唯一后继, 现在只不过是去指向其唯一前趋.

基本的思路是:

  1. 需要三个指针, 一个指向前趋, 一个指向当前结点, 一个指向后继;
  2. 然后循环迭代, 变换指针的移动即可.

以上的是最基本的迭代思维, 那么尝试使用递归的思想来解决呢?

  1. 首先递归反转某个结点后的所有链表;
  2. 直至base case: 空链或唯一结点;
  3. 然后将反转后的链表与该结点连接上即可.

解题1

首先是迭代的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head) {
    if(head == nullptr)
        return nullptr;
    ListNode *h = nullptr;
    ListNode * p = head, *q = head;
    while(p != nullptr && p->next != nullptr){
        q = p->next;
        p->next = h;
        h = p;
        p = q;
    }
    p->next = h;
    return p;
}

然后是递归的解法, 最后三行不好理解的话画个图就知道了:

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseList(ListNode* head) {
    if(head == nullptr || head->next == nullptr){
        return head;
    }
    // 使用last指向翻转head后的链表
    ListNode *last = reverseList(head->next);
    // 这里需要画个图才能解释
    head->next->next = head;
    // 最后head去指向空
    head->next = nullptr;
    return last;
}

反转部分链表

题目2

首先来看题目92. 反转链表 II: 给你单链表的头指针 head 和两个整数 left 和 right, 其中 left <= right . 请你反转从位置 left 到位置 right 的链表节点, 返回反转后的链表.

示例1:

输入: head = [1,2,3,4,5], left = 2, right = 4

输出: [1,4,3,2,5]

示例2:

输入: head = [5], left = 1, right = 1

输出: [5]

理解一下2

与上一题不同的是, 这题需要将链表的部分区间进行翻转, 这就需要将链表分为三个部分处理: 前部分-翻转部分-后部分, 这会显得比较麻烦.

那么我们考虑一个问题: 反转链表前N个结点, 那么链表就只需要分为: 翻转部分-后部分, 相比而言简单一些了.

反转前N个结点的基本的思路是:

  1. 通过N设置对反转结束的判断, 同时需要一个指针来表示后继;
  2. 与第一题一样翻转;

那么对于我们的区间就很简单了:

  1. 不断递归或迭代后移至需要反转的结点;
  2. 然后不就是反转链表前N个结点的问题嘛!

解题2

由于结点和指针相对较多, 要仔细判断清楚.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if(left == 1)
        return reverseTopN(head, right);
    head->next = reverseBetween(head->next, left-1, right-1);
    return head;
}

ListNode * rest;
ListNode* reverseTopN(ListNode* head, int n){
    if(n == 1){
        rest = head->next;
        return head;
    }
    ListNode * last = reverseTopN(head->next, n-1);
    head->next->next = head;
    head->next = rest;
    return last;
}

个人收获

在这里反转链表的问题上, 迭代和递归的时间复杂度都是O(n), 所以选择使用哪个都差不多, 但是递归的空间复杂度却是O(n), 所以实际应用的时候还是迭代较好.

不过这里让我对递归有了更好的认知, 写递归函数, 就是要相信这个递归函数可以做到它该做的, 然后我们将base case和其他需要准备的做好就可以了, 剩下的就相信它!

------ 本文结束------