反转单链表

发表于 分类于 ， 阅读次数： Waline： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

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

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

思路：

方法一： 递归

对于递归算法，最重要的就是明确递归函数的定义，不要跳进具体的细节中。

比如对于这道题，递归函数reverseList的定义就是：

输入一个节点head，将以head为起点的链表反转，并返回反转后的头节点。

比如我们反转

我们经过

1
ListNode *dummy = reverseList(head->next);

之后，整个链表就变为了：

此时我们只需要让2指向1，1指向nullptr，然后返回dummy即：

1
2
3
head->next->next = head;
head->next = nullptr;
return dummy;

我们就得到了：

最后，递归函数需要有终止条件base case：

1
2
3
if(head == nullptr || head->next == nullptr){
  	return head;
}

综上，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode *dummy = reverseList(head->next);
        //使末尾指针指向当前节点
        head->next->next = head;
        //让新链表的尾节为空，避免成环
        head->next =  nullptr;
        return dummy;
    }
};

迭代：

我们采用头插法来实现：

直到cur==nullptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        //头插法
        while(cur != nullptr){
            ListNode *t = cur->next;
            cur->next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
};

92. 反转链表 II

给你单链表的头指针 head和两个整数 left和 right，其中 left <= right。请你反转从位置 left到位置 right的链表节点，返回 反转后的链表 。

示例：

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

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

思路：

方法一：递归

在解决这道题之前。如果需要我们只反转开头的前m个元素，我们如何解决呢？

例如：

reverse(head, 3)

思路和我们前面一题反转全部链表差不多，我们只需要记录反转的节点个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode *succ = nullptr;    //后驱节点

//反转以 head 为起点的 n 个节点，返回新的头节点
ListNode* reverseN(ListNode *head, int n){
    if(n == 1){
        //记录第 n + 1 个节点
        succ = head->next;
        return head;
    }
     // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode *last = reverseN(head->next, n - 1);
    head->next->next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head->next = succ;
    return last;
}

现在我们再来解决这道题，如果left = 1，也就是我们刚才实现的功能。

如果 left != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 left 个元素开始反转对吧；如果把 head->next 的索引视为 1 呢？那么相对于 head->next，反转的区间应该是从第 left - 1 个元素开始的；那么对于 head->next->next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
  	ListNode *succ = nullptr;    //后驱节点

    //反转以 head 为起点的 n 个节点，返回新的头节点
    ListNode* reverseN(ListNode *head, int n){
        if(n == 1){
            //记录第 n + 1 个节点
            succ = head->next;
            return head;
        }
         // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode *last = reverseN(head->next, n - 1);
        head->next->next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head->next = succ;
        return last;
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //base case
        if(left == 1){
            return reverseN(head, right);
        }
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }
};

方法二：迭代

同样采用头插法，先找到left节点的左边一个节点pre

将left所在的节点定义为cur，cur下一个节点为next

  • 把cur的下一个节点指向next的下一个节点
  • 把next的下一个节点指向pre的下一个节点
  • 把pre的下一个节点指向next

即

1
2
3
4
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;

以此类推right - left次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        for(int i = 0; i < left - 1; i++){
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for(int i = 0; i < right - left; i++){
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummy->next;
    }
};