C++交换两个链表中的节点

唯·爱

1. C++编程交换两个链表中的节点
   
2. 
   
3. ```cpp
   
4. #include <iostream>
   
5. 
   
6. using namespace std;
   
7. 
   
8. // 定义链表节点结构体
   
9. struct ListNode {
   
10.     int val;
    
11.     ListNode* next;
    
12.     ListNode(int x) : val(x), next(NULL) {}
    
13. };
    
14. 
    
15. // 交换两个链表中的节点
    
16. void swapNodes(ListNode** head, int x, int y) {
    
17.     // 如果x和y相同，无需交换
    
18.     if (x == y) {
    
19.         return;
    
20.     }
    
21. 
    
22.     // 定义两个指针，用于记录需要交换的节点和它们的前一个节点
    
23.     ListNode* prevX = NULL;
    
24.     ListNode* currX = *head;
    
25.     ListNode* prevY = NULL;
    
26.     ListNode* currY = *head;
    
27. 
    
28.     // 找到需要交换的节点和它们的前一个节点
    
29.     while (currX && currX->val != x) {
    
30.         prevX = currX;
    
31.         currX = currX->next;
    
32.     }
    
33. 
    
34.     while (currY && currY->val != y) {
    
35.         prevY = currY;
    
36.         currY = currY->next;
    
37.     }
    
38. 
    
39.     // 如果x或y不在链表中，直接返回
    
40.     if (!currX || !currY) {
    
41.         return;
    
42.     }
    
43. 
    
44.     // 如果x是头节点，则更新头指针
    
45.     if (prevX == NULL) {
    
46.         *head = currY;
    
47.     } else {
    
48.         prevX->next = currY;
    
49.     }
    
50. 
    
51.     // 如果y是头节点，则更新头指针
    
52.     if (prevY == NULL) {
    
53.         *head = currX;
    
54.     } else {
    
55.         prevY->next = currX;
    
56.     }
    
57. 
    
58.     // 交换节点的next指针
    
59.     ListNode* temp = currX->next;
    
60.     currX->next = currY->next;
    
61.     currY->next = temp;
    
62. }
    
63. 
    
64. // 打印链表
    
65. void printList(ListNode* node) {
    
66.     while (node) {
    
67.         cout << node->val << " ";
    
68.         node = node->next;
    
69.     }
    
70.     cout << endl;
    
71. }
    
72. 
    
73. int main() {
    
74.     // 创建链表1: 1->2->3->4->5
    
75.     ListNode* head1 = new ListNode(1);
    
76.     head1->next = new ListNode(2);
    
77.     head1->next->next = new ListNode(3);
    
78.     head1->next->next->next = new ListNode(4);
    
79.     head1->next->next->next->next = new ListNode(5);
    
80. 
    
81.     // 创建链表2: 6->7->8->9->10
    
82.     ListNode* head2 = new ListNode(6);
    
83.     head2->next = new ListNode(7);
    
84.     head2->next->next = new ListNode(8);
    
85.     head2->next->next->next = new ListNode(9);
    
86.     head2->next->next->next->next = new ListNode(10);
    
87. 
    
88.     cout << "交换前的链表1: ";
    
89.     printList(head1);
    
90.     cout << "交换前的链表2: ";
    
91.     printList(head2);
    
92. 
    
93.     // 交换链表1中的节点2和节点4
    
94.     swapNodes(&head1, 2, 4);
    
95. 
    
96.     // 交换链表2中的节点7和节点9
    
97.     swapNodes(&head2, 7, 9);
    
98. 
    
99.     cout << "交换后的链表1: ";
    
100.     printList(head1);
     
101.     cout << "交换后的链表2: ";
     
102.     printList(head2);
     
103. 
     
104.     return 0;
     
105. }
     
106. ```
     
107. 
     
108. 我们首先定义了一个链表节点的结构体`ListNode`，包含一个整数值`val`和一个指向下一个节点的指针`next`。
     
109. 
     
110. 然后，我们定义了一个`swapNodes`函数，用于交换两个链表中的节点。该函数接受一个指向头节点指针的指针`head`，以及两个需要交换的节点的值`x`和`y`。函数首先判断`x`和`y`是否相同，如果相同则无需交换。然后，定义了四个指针`prevX`、`currX`、`prevY`和`currY`，分别指向需要交换的节点和它们的前一个节点。通过遍历链表找到这两个节点。如果找不到其中一个节点，则直接返回。接着，更新头指针和交换节点的`next`指针，完成节点交换。
     
111. 
     
112. 最后，在`main`函数中，我们创建了两个链表，并调用`swapNodes`函数交换链表中的节点。然后，打印交换前后的链表。

复制代码