Reverse Part List

发表于 | 分类于

Reverse Part List

题目描述：

给定一个链表的头结点，然后指定起始位置m和终止位置n；要求逆序链表中从第m个节点到n个节点的部分。

例子：

详细描述可以看LeetCode92。

解题思路：

链表的题目需要注意的是关于头节点的处理。我们定义了一个虚拟头节点用来处理这种情况；另外需要注意的是关于链表被逆序后的重新连接的问题，我们在开始部分需要找到需要逆序部分的上一个节点和下一个节点用来将逆序结果重新连接到链表中。

代码如下：

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
45
46
47
48
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || (m == n)) return head;
        # 如果是空链表或者起始位置和终止位置相同，则直接返回
        ListNode* dummy = new ListNode(-1);
        # 定义虚拟头结点
        dummy->next = head;
        ListNode* pre = dummy;
        # 定义前节点
        ListNode* back = head;
        # 定义后节点
        while(m - 1 > 0){
            pre = pre->next;
            m--;
        }
        # 找到待逆序节点的前一个位置
        ListNode* front = pre->next;
        # 逆序部分的第一个节点
        while(n - 1 > 0){
            back = back->next;
            n--;
        }
        # 逆序部分的尾节点
        ListNode* next = back->next;
        # 逆序部分尾部的下一个节点
        
        ListNode* left = front;
        ListNode* right = front->next;
        # 定义逆序部分的前后节点
        left->next = NULL;
        # 前节点next指针改变
        while(right != next){
            ListNode* tmp = right->next;
            # 保存好下一个指针
            right->next = left;
            # 逆序前后位置
            left = right;
            # 前指针前进一个位置
            right = tmp;
            # 后指针前进一个位置
        }
        pre->next = left;
        front->next = next;
        # 重新连接链表的头和尾
        return dummy->next;     
    }
};