leetcode 92.反转链表2

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

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

举例：

链表：

graph LR
0 --> 1
1 --> 2
2 --> 3
3 --> 4
4 --> 5
5 --> 6
6 --> 7
7 --> 8
8 --> 9

反转位置3到7，反转后的链表为：

graph LR
0 --> 1
1 --> 2
2 --> 7
7 --> 6
6 --> 5
5 --> 4
4 --> 3
3 --> 8
8 --> 9

由上图可知，先将链表切割成0到2，3到7，8到9，反转链表3到7，然后重新链接即可。
切割链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//head是链表头节点，left表示反转的左端，right表示反转的右端
ListNode* leftNode = head;
ListNode* middleNode;
ListNode* rightNode;
ListNode* tNode;
for(int i = 0; i <= right; ++i){
    if(i < left) leftNode = leftNode->next;
    else if(i == left) {
        middleNode = leftNode->next;
        leftNode->next = NULL;
        tNode = middleNode;
    }
    else if(i < right){
        tNode = tNode->next;
    }
    else if(i == right){
        rightNode = tNode->next;
        tNode->next = NULL;
    }
}

此时各节点情况如下：

graph BT
leftNode --> 2
middleNode --> 3
tNode --> 6
rightNode --> 7

对以middleNode开始，以tNode结束的链表进行反转。

从前往后一次遍历反转链表，步骤：

  1. 保存当前节点的子节点指针

  2. 当前节点作为头节点，当前节点指向头节点

  3. 更新头节点指针，指向当前节点

  4. 更新当前节点指针，指向子节点

1
2
3
4
5
6
7
8
9
ListNode* pre = NULL;
ListNode* cur = middleNode;

while(cur != NULL){
    ListNode* next = cur->next;
    cur->next = pre;
    pre = cur;
    cur = next;
}

反转完成后，原头节点指针middleNode指向尾节点，原尾节点指针tNode指向头节点。

将leftNode节点指向middleNode节点，tNode节点指向rightNode节点即可。

1
2
leftNode->next = tNode;
middleNode->next = rightNode;

最后head指向的链表即完成了反转。