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

题目链接

原本以为链表是比较容易对付的知识点,但规模比较大的问题很容易在思考完成写代码的时候出现混乱,引发难以debug的问题.用画图这种更形象的方法可以比较有效的解决思路紊乱的问题.

测试用例和示意图
输入：head = [1,2,3,4]
输出：[2,1,4,3]

这道题的操作规模并不算很大,题目要求我们把链表中成对的结点两两交换后输出.很容易想到用迭代或者递归进行next结点的交换就可以解决问题,但在交换的顺序上需要用画图理清逻辑.

链表已经被定义好,val为值,next指向下一个结点的引用.

// 链表结点的定义,不需要写在程序里
public class ListNode {
	int val;
	ListNode next;
	
	ListNode() {}
	
	ListNode(int val) {this.val = val;}
	
	ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

看着示意图不难理清思路,以新定义的头结点作为起点(nowNode),交换后两个结点(leftNode和rightNode)在链表中的顺序,然后将交换后连接后方结点的结点设置为flag,继续执行交换,直到后方的结点不足两个.

操作前的链表长这样:

最后要达到的效果:

用代码实现.首先由于涉及到头结点
的移动,我们设置一个空结点重新作为头结点.交换的起点也是它.

ListNode dummyHead = new ListNode(-1,head);
ListNode nowNode = dummyHead;
1
2

对于每一个结点,作出交换操作,如果后面没有结点需要交换就直接退出循环

while (nowNode.next != null && nowNode.next.next != null) {
			ListNode leftNode = nowNode.next;
			ListNode rightNode = nowNode.next.next;
			
			leftNode.next = rightNode.next;
			rightNode.next = leftNode;
			nowNode.next = rightNode;
			nowNode = leftNode;
		}
1
2
3
4
5
6
7
8
9

最后返回虚拟头结点的next,也就是交换后真正的头结点

return dummyHead.next;
1

主要的难点在于交换的过程怎么实现.在每次交换开始时的情况就和上面的一样.

声明好临时变量之后,第一个操作用来把rightNode的next结点交给leftNode的next结点.因为前三个结点的next都需要指向新的结点,而已经有临时变量存放它们的引用,所以优先把待会会被覆盖的rightNode,next放到正确的位置.这时候示意图长这样

其他两个需要更改的next指针指向的引用都已经存放在变量中了,所以顺序不是那么重要.之后变成这样

但原来的rightNode.next结点引用,现在存放在leftNode.next中.
所以设置leftNode结点作为下一个交换的开始,检测后两个需要交换的结点是否存在.

nowNode后结点不够的情况已经在循环条件中考虑,而nowNode结点永远不会为空,因为初始值为自行创建的虚拟头结点,在满足交换条件并执行交换之后才会更新.

由于每一对结点都需要进行操作,所以时间复杂度为$O(n)$.代码使用常数个变量,空间复杂度为$O(1)$.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode swapPairs(ListNode head) {
		ListNode dummyHead = new ListNode(-1,head);
		ListNode nowNode = dummyHead;
		while (nowNode.next != null && nowNode.next.next != null) {
			ListNode leftNode = nowNode.next;
			ListNode rightNode = nowNode.next.next;
			
			leftNode.next = rightNode.next;
			rightNode.next = leftNode;
			nowNode.next = rightNode;
			nowNode = leftNode;
		}
		
		return dummyHead.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