NC21 链表内指定区间反转（链表）_nc21 链表内指定区间反转 c实现

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转
要求时间复杂度 O(n)，空间复杂度 O(1)
例如：
给出的链表为1→2→3→4→5→NULL, m=2,n=4,
返回 1→4→3→2→5→NULL.

解题思路

反转局部链表，可以将该局部部分当作完整链表进行反转
再将已经反转好的局部链表与其他节点建立连接，重构链表
使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。

class Solution {
public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0);//设置虚拟头节点
        ListNode* pre = dummy;
        dummy->next=head;
        //走left-1步到left的前一个节点
        for(int i=0;i<m-1;i++){
            pre=pre->next;
        }
        //走roght-left+1步到right节点
        ListNode* right=pre;
        for(int i=0;i<n-m+1;i++){
            right=right->next;
        }
        //截取出一个子链表
        ListNode* left=pre->next;
        ListNode* cur=right->next;
        //切断链接
        pre->next=nullptr;
        right->next=nullptr;
        //反转局部链表
        reverse(left);
        //接回原来的链表
        pre->next=right;
        left->next=cur;
        return dummy->next;
    }
    ListNode* reverse(ListNode* head){
        ListNode* pre=new ListNode(0);
        ListNode* cur=head;
        ListNode* next=nullptr;
        while(cur!=nullptr){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};
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