【算法与数据结构】24、LeetCode两两交换链表中的节点

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：题目要求两两交换节点。在链表当中非常重要就是下一个节点，一旦丢失，这个节点后面的节点也就找不到了。那么我们在需要再交换前后做好保存节点变量的工作，程序当中我们设置了两个临时变量，例如在[1 2 3 4]这个链表当中，第一次交换(交换1 2 节点)，cur指向虚节点，tmp1指向第一个节点（也就是1），tmp2需要指向第三个节点，因此修改指针的过程中会丢失。首先，让cur节点指向第2个节点，第2个节点指向第1个节点，第1个节点指向第3个节点，这样就完成了第一次交换。其次，我们做更新操作，注意第一次交换是三个指针的相对位置(tmp1是cur的下一个节点，tmp2是tmp1的next next节点)，因此下一次循环也循序这个规则。

  程序如下：

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		ListNode* FakeNode = new ListNode(0, head);
		ListNode* tmp1;	// 临时变量
		ListNode* tmp2;	// 临时变量
		ListNode* cur = FakeNode;	// 头结点的下一个节点
		while (cur->next != NULL && cur->next->next != NULL) {
			// 更新
			tmp1 = cur->next;			// 保存第1个节点，虚节点是第0个节点
			tmp2 = tmp1->next->next;	// 保存第3个节点
			//交换
			cur->next = tmp1->next;		
			cur->next->next = tmp1;
			tmp1->next = tmp2;
			// 更新
			cur = tmp1;
		}
		return FakeNode->next;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度： $O(n)$。
• 空间复杂度：$O(1)$。

三、完整代码

# include 
using namespace std;

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* FakeNode = new ListNode(0, head);
		ListNode* tmp1;	// 临时变量
		ListNode* tmp2;	// 临时变量
		ListNode* cur = FakeNode;	// 头结点的下一个节点
		while (cur->next != NULL && cur->next->next != NULL) {
			// 更新
			tmp1 = cur->next;			// 保存第1个节点，虚节点是第0个节点
			tmp2 = tmp1->next->next;	// 保存第3个节点
			//交换
			cur->next = tmp1->next;		
			cur->next->next = tmp1;
			tmp1->next = tmp2;
			// 更新
			cur = tmp1;
		}
		return FakeNode->next;
	}
};

ListNode* ChainGenerator(int arr[], int len) {
	ListNode* head = new ListNode(arr[0], NULL);
	ListNode* p = head;
	for (int i = 1; i < len; i++) {
		ListNode* pNewNode = new ListNode(arr[i], NULL);
		p->next = pNewNode; // 上一个节点指向这个新建立的节点
		p = pNewNode; // p节点指向这个新的节点
	}
	return head;
}

void my_print(ListNode* head, string str) {
	cout << str << endl;
	ListNode* cur = head;
	while (cur != NULL) {
		cout << cur->val << ' ';
		if (cur->next == NULL) break;
		cur = cur->next;
	}
	cout << endl;
}

int main()
{
	//int arr[] = { 1,2,3,4 };
	int arr[] = { 1 };
	int len = sizeof(arr) / sizeof(int);
	Solution s1;
	ListNode* head = ChainGenerator(arr, len);
	my_print(head, "目标链表：");
	head = s1.swapPairs(head);
	my_print(head, "翻转后的链表：");
	system("pause");
	return 0;
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

end