刷题笔记day04-链表

24. 两两交换链表中的节点

/**
 * 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* swapPairs(ListNode* head) {
        // 增加空头节点，利于后续交换
        ListNode *newHead = new ListNode;
        newHead -> next = head;
        ListNode *curr = newHead;

        ListNode *tmp;
        ListNode *tmp1;

        // 一次性判断两个，curr和next，因为交换是两个一起的，所以不足就不交换
        while (curr->next != nullptr && curr -> next -> next != nullptr) {
            tmp = curr -> next;
            tmp1 = curr -> next -> next -> next;  // 下一组（两个一组）的第一个节点
            // curr下一个指向2
            curr -> next = curr -> next -> next;
            // 2下一个指向1
            curr -> next -> next = tmp;
            // 2下一个指向下一组
            tmp -> next = tmp1;

            // 往后移动两位，开始交换下一组节点
            curr = curr -> next -> next;

        }

        return newHead->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