206、反转链表

[反转链表][https://leetcode.cn/problems/reverse-linked-list/]

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

三个变量来控制，一个为当前节点，一个为前置节点，一个为后置节点，将当前节点的下个置为前置，将后置的下个置为当前，前置变为当前，当前变为下个。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* next;

        while(cur){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
            
        }
        return pre;
    }
};

92、反转链表2

[反转链表2][https://leetcode.cn/problems/reverse-linked-list-ii/description/]

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

首先找到left指向的节点

然后进行反转

反转结束后，pre指向right节点 cur指向right+1的节点

我们需要将left-1的节点指向pre

将left节点指向cur

由于会有left = 1的情况，此时需要加入哨兵节点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* p0 = dummy;
        while(left > 1){
            p0 = p0->next;
            left --;
            right --;
        }
        ListNode* pre = nullptr;
        ListNode* cur = p0->next;
        ListNode* next = new ListNode();

        while(right > 0){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
            right --;
        }
        p0->next->next = cur;
        p0->next = pre;
        
        return dummy->next;

    }
};
25、K 个一组翻转链表

[K 个一组翻转链表][https://leetcode.cn/problems/reverse-nodes-in-k-group/]

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

首先，需要计算链表的长度，方便后面计算

其次，需要新增变量报错开始翻转前的一个节点，即dummy。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while(cur){
            n ++;
            cur = cur->next;
        }
        ListNode* dummy = new ListNode(-1, head);
        ListNode* d0 = dummy;

        while(n >= k){
            n -= k;
            ListNode* pre = nullptr;
            cur = d0->next;
            int i = 0;
            while(i < k){
                i ++;
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            ListNode* d1 = d0->next;
            d0->next->next = cur;
            d0->next = pre;
            d0 = d1;
        }
        return dummy->next;
    }
};