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

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 238 阅读时长 ≈ 1 分钟

考点

  • 链表的反转

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public:
		ListNode* swapPairs(ListNode* head) {
			ListNode *dummyHead = new ListNode(-1, head);
			ListNode *subDummy = dummyHead;
			while (subDummy->next != nullptr && subDummy->next->next != nullptr) {
				ListNode *nodeOne = subDummy->next;
				ListNode *nodeTwo = subDummy->next->next;
				nodeOne->next = nodeTwo->next;
				nodeTwo->next = subDummy->next;
				subDummy->next = nodeTwo;
				subDummy = nodeOne;
			}
			return dummyHead->next;
		}
};

思路

题目说两两交换其中相邻的节点，我完全可以理解为：

执行若干次反转长度为2的子链表操作

那么就可以使用改进版头插法完成这一操作

设每个子链表的dummyHead名称为subDummy，子链表的第一个节点名称为nodeOne，第二个节点名称为nodeTwo

子链表{1, 2}反转结束后，可以发现nodeOne所处的位置恰好就是下一个子链表{3, 4}的subDummy

故而将nodeOne赋值给subDummy后开启下一轮反转

子链表{3, 4}反转结束后，发现子链表{5}长度不等于2，结束循环