92 反转链表 II

本文最后更新于：2021年4月7日 晚上

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

Solution

  • 迭代翻转

  • 先拆分成三段，前段+翻转段（中段）+后段

  • link1 表示前段最后一个节点

  • link2 表示翻转前中段的第一个节点，也是翻转后中段的最后一个节点

  • link3 表示翻转后中段的第一个节点

  • link4 表示后段的第一个节点

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
28
29
30
31
32
33
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head:
            return None
        res = ListNode(0)
        res.next = head
        result = res
        
        for _ in range(m):
            link1 = res
            res = res.next
        
        link2 = res
        link3 = None
        link4 = None
        for _ in range(n-m+1):
            link4 = res.next
            res.next = link3
            link3 = res
            res = link4
        
        link1.next = link3
        link2.next = link4
        return result.next
        
# @lc code=end
  • 递归法

参考：《算法小抄》3.10 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        self.successor = None
        def reverseN(head, n):
            if n==1:
                self.successor = head.next
                return head
            last = reverseN(head.next, n-1)
            head.next.next = head
            head.next = self.successor
            return last
        
        if m==1:
            res = reverseN(head, n)
            return res
        head.next = self.reverseBetween(head.next, m-1, n-1)
        return head

cpp

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
28
29
30
31
32
33
34
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==1){
            ListNode* ret = reverseN(head, n);
            return ret;
        }
        head->next = reverseBetween(head->next, m-1, n-1);
        return head;
    }
private:
    ListNode* successor = NULL;

    ListNode* reverseN(ListNode* head, int n){
        if(n==1){
            successor = head->next;
            return head;
        }
        ListNode* rhead = reverseN(head->next, n-1);
        head->next->next = head;
        head->next = successor;
        return rhead;
    }
};
// @lc code=end

反转时用迭代

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
28
29
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == 1) {
            ListNode* ret = reverse(head, right);
            return ret;
        }
        head->next = reverseBetween(head->next, left-1, right-1);
        return head;
    }

    ListNode* reverse(ListNode* head, int n) {
        if (n == 1) {
            return head;
        }

        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nex = nullptr;
        for (int i = 0; i < n; ++i) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        head->next = nex;
        return pre;
    }
};
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！