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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

 

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

解题思路：

1、当涉及对链表头结点进行操作，且头结点可能为空时，不妨创建哑结点；

 2、创建初始状态

3、先处理前驱节点pre和node1节点，pre->next指向node2和node1->next指向node2->next：

 

4、再处理当前节点node2->next指向node1：

 5、状态后移pre指向node1，node1指向node1->next，node2指向node1->next：

 

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 class ListNode {
 7 public:
 8     ListNode() : val(0), next(nullptr) {}
 9     ListNode(int x) : val(x), next(nullptr) {}
10     ListNode(int x, ListNode *next) : val(x), next(next) {}
11 
12 public:
13     int val;
14     ListNode *next;
15 };
16 
17 class Solution {
18 public:
19     ListNode* swapPairs(ListNode* head) {
20         if (head == nullptr) {
21             return nullptr;
22         }
23         // 创建哑结点
24         ListNode *dummyNode = new ListNode(0);
25         dummyNode->next = head;
26         // 建立初始状态
27         ListNode *pre = dummyNode;
28         ListNode *node1 = head;
29         ListNode *node2 = head->next;
30 
31         while (node1 != nullptr && node1->next != nullptr) {
32             // 先处理前驱节点状态(pre和node1)
33             pre->next = node2;
34             node1->next = node2->next;
35             // 处理当前节点
36             node2->next = node1;
37             // 状态后移
38             pre = node1;
39             node1 = node1->next;
40             if (node1->next != nullptr) {
41                 node2 = node1->next;
42             }
43         }
44         ListNode *newHead = dummyNode->next;
45         delete dummyNode;
46         return newHead;
47     }
48     // 尾插法插入链表元素
49     void insertNodeAtTail(ListNode *&head, int val) {
50         ListNode *newNode = new ListNode(val);
51         ListNode *currentNode = head;
52         if (head == nullptr) {
53             head = newNode;
54             return;
55         }
56         while (currentNode->next != nullptr) {
57             currentNode = currentNode->next;
58         }
59         currentNode->next = newNode;
60         return;
61     }
62     // 打印链表元素
63     void printfListNode(ListNode *head) {
64         while (head != nullptr) {
65             std::cout << head->val << "->";
66             head = head->next;
67         }
68         std::cout << "NULL" << endl;
69         return;
70     }
71 };
72 int main()
73 {
74     Solution *test = new Solution();
75     vector<int> vec = {1, 2, 3, 4, 5, 6, 7 };
76     ListNode *head = nullptr;
77     // 插入节点
78     for (const auto &v : vec) {
79         test->insertNodeAtTail(head, v);
80     }
81     test->printfListNode(head); // 1->2->3->4->5->6->7->NULL
82     ListNode *swapedHead = test->swapPairs(head);
83     test->printfListNode(swapedHead); // 2->1->4->3->6->5->7->NULL
84 
85     delete test;
86     system("pause");
87     return 0;
88 }

6、运行结果：