Leetcode经典链表问题之反转链表

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseList(ListNode* head) {
14
        ListNode* prev = nullptr;
15
        ListNode* next = nullptr;
16
        ListNode* temp = head;
17
        while(temp!= nullptr){
18
            next = temp -> next;
19
            temp -> next = prev;
20
            prev = temp;
21
            temp = next;
22
        }
23
        return prev;
24
    }
25
};

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseBetween(ListNode* head, int left, int right) {
14
        ListNode* dummy = new ListNode(0);
15
        dummy->next = head;
16
        ListNode* p0 = dummy;
17
        for(int i = 1;i < left;i++){    //i 从1开始，移动left- 1次，指向left前一个节点
18
            p0 = p0->next;
19
        }
20
        ListNode* prev = nullptr;   // 不是p0
21
        ListNode* cur = p0 -> next;
22
        for(int i = left ;i <= right;i++){
23
            ListNode* next = cur->next;
24
            cur -> next = prev;
25
            prev = cur;
26
            cur = next;
27
        }
28
        p0 -> next -> next = cur;
29
        p0 -> next = prev;
30
        return dummy -> next;
31
    }
32
};
33
### 关于哨兵节点
34

35

36
** 哨兵节点的作用**
37

38

39
**✅ (1) 确保 m-1 位置正确连接**
40

41

42
• 反转部分链表时，m-1 位置的节点需要正确指向反转后的 m 位置。
43

44

45
• 哨兵节点 dummy 让 prev 总是存在，无论 m=1 还是 m>1，都可以通过 dummy->next 访问 m-1 位置。
46

47

48
**✅ (2) 处理 m=1 的情况，防止 head 丢失**
49

50

51
• 反转部分链表时，如果 m=1，head 需要更新。
52

53

54
• 如果直接修改 head，可能导致 head 丢失，难以返回正确的新头。
55

56

57
• 使用 dummy，dummy->next 总是指向 head，即使 head 改变，我们仍然可以返回 dummy.next，保证正确性。
58

59

60
## 25. K 个一组翻转链表 - 力扣（LeetCode）
61

62

63
```cpp
64
/**
65
 * Definition for singly-linked list.
66
 * struct ListNode {
67
 *     int val;
68
 *     ListNode *next;
69
 *     ListNode() : val(0), next(nullptr) {}
70
 *     ListNode(int x) : val(x), next(nullptr) {}
71
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
72
 * };
73
 */
74
class Solution {
75
public:
76
    ListNode* reverseKGroup(ListNode* head, int k) {
77
        int n = 0;
78
        ListNode* temp = head;
79
        while(temp){
80
            n++;
81
            temp = temp -> next;
82
        }
83
        ListNode dummy(0,head);
84
        ListNode* p0 = &dummy;
85
        ListNode* prev = nullptr;
86
        ListNode* cur = head;
87
        for(;n >= k; n -= k){
88
            for(int i = 0; i < k ;i++){
89
                ListNode* next= cur->next;
90
                cur -> next = prev;
91
                prev = cur;
92
                cur = next;
93
            }
94
            ListNode* nxt = p0->next;
95
            p0 -> next -> next = cur;
96
            p0 -> next = prev;
97
            p0 = nxt;
98
        }
99
        return dummy.next;
100
    }
101
};