c++之单链表的三种反转_c++单链表反转

在刷LeetCode题时，链表的反转可分三种情况：
1、反转整个链表
2、反转其中连续的一部分
3、分段反转

一、反转整个链表
Leetcode206. 反转链表

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(NULL==head || NULL==head->next) return head;

        ListNode *cur=NULL;
        ListNode *pre=head;
        while(pre)
        {
            ListNode *t=pre->next;
            pre->next=cur;
            cur=pre;
            pre=t;
        }
        return cur;
    }
};
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

二、反转单链表其中连续的一部分
LeetCode92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

/**
 * 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) {
    //使用dummy node
        ListNode *dummy=new ListNode(-1);
        dummy->next=head;

        ListNode *pre=dummy;
        for(int i=1;i<m;i++)
            pre=pre->next;

        ListNode *t,*cur=pre->next,*mNode=pre->next;
        for(int i=0;i<n-m+1;i++)
        {//头插入法，一个一个节点的进行插入
            t=cur->next;
            cur->next=pre->next;
            pre->next=cur;
            cur=t;
        }
        mNode->next=cur;
        return dummy->next;
    }
};
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

三、分段反转

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

可使用二、反转单链表其中连续的一部分来求解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int num=0;
        ListNode *head1=head;
        while(head1)
        {
            num++;
            head1=head1->next;
        }
        ListNode *dummy1=new ListNode(-1);
        dummy1->next=head;
        int l=1;
        while(l+k-1<=num)
        {
            dummy1->next=reverseBetween(dummy1->next,l,l+k-1);
            l=l+k;
        }
        return dummy1->next;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *dummy=new ListNode(-1);
        dummy->next=head;

        ListNode *pre=dummy;
        for(int i=1;i<m;i++)
            pre=pre->next;

        ListNode *t,*cur=pre->next,*mNode=pre->next;
        for(int i=0;i<n-m+1;i++)
        {
            t=cur->next;
            cur->next=pre->next;
            pre->next=cur;
            cur=t;
        }
        mNode->next=cur;
        return dummy->next;
    }
};
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
49