LeetCode 92. 反转链表 II（双指针）

107 阅读 0 评论 71 点赞

我是靠谱客的博主轻松月饼，这篇文章主要介绍LeetCode 92. 反转链表 II（双指针），现在分享给大家，希望可以做个参考。

1. 题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。

复制代码

1
2
3
4
5
示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

把要反转的片段断开，反转之，在跟前后接起来，好理解吧

复制代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *emptyHead = new ListNode(-1);//为了方便加个哨兵
        emptyHead->next = head;
        ListNode *leftend = emptyHead, 
        		*rightstart = emptyHead;//反转段前后的两个节点
        ListNode *revStart, *revEnd;//需要反转的开始终点

while(n--)//右边的先过去，不然左边断开了，过不去了
            rightstart = rightstart->next;
        revEnd = rightstart;
        rightstart = rightstart->next;
        revEnd->next = NULL;//断开需要反转的右端点

while(--m)
            leftend = leftend->next;
        revStart = leftend->next;
        leftend->next = NULL;//断开需要反转的左端点

reverseList(revStart, revEnd);//反转中间段（传入引用，首尾交换了）
        leftend->next = revStart;
        revEnd->next = rightstart;
        return emptyHead->next;
    }

void reverseList(ListNode* &head, ListNode* &tail)//传入的是引用
    {
        tail = head;//尾巴是现在的起点
        ListNode *tempH = head;
        if(!tempH || !tempH->next)
            return;
        ListNode *prev = NULL, *nexNode;
        while(tempH)
        {
            nexNode = tempH->next;
            tempH->next = prev;
            prev = tempH;
            tempH = nexNode;
        }
        head = prev;//起点是现在的尾巴
    }
};

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
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *emptyHead = new ListNode(-1);//为了方便加个哨兵
        emptyHead->next = head;
        ListNode *leftend = emptyHead, 
        		*rightstart = emptyHead;//反转段前后的两个节点
        ListNode *revStart, *revEnd;//需要反转的开始终点

        while(n--)//右边的先过去，不然左边断开了，过不去了
            rightstart = rightstart->next;
        revEnd = rightstart;
        rightstart = rightstart->next;
        revEnd->next = NULL;//断开需要反转的右端点

        while(--m)
            leftend = leftend->next;
        revStart = leftend->next;
        leftend->next = NULL;//断开需要反转的左端点

        reverseList(revStart, revEnd);//反转中间段（传入引用，首尾交换了）
        leftend->next = revStart;
        revEnd->next = rightstart;
        return emptyHead->next;
    }

    void reverseList(ListNode* &head, ListNode* &tail)//传入的是引用
    {
        tail = head;//尾巴是现在的起点
        ListNode *tempH = head;
        if(!tempH || !tempH->next)
            return;
        ListNode *prev = NULL, *nexNode;
        while(tempH)
        {
            nexNode = tempH->next;
            tempH->next = prev;
            prev = tempH;
            tempH = nexNode;
        }
        head = prev;//起点是现在的尾巴
    }
};