代码随想录刷题day13|（链表篇）24.两两交换链表中的结点

目录

一、链表理论基础

二、思路及易错点

易错点

三、相关算法题目

四、错误代码分析

---

一、链表理论基础

代码随想录 (programmercarl.com)

二、思路及易错点

该题使用虚拟头结点正常进行模拟即可，有两个关键点，一是循环何时终止？终止条件怎么写？二是交换结点的顺序；

易错点

1.如何确定循环终止的条件？

首先，在进行交换时，一定要知道被交换结点的前一个结点，当前指针一定要指向2个交换结点的前一个结点，才可以进行操作；

假设当前有奇数个结点[0,1,2,3,4,5]（0代表虚拟结点），指向0，操作1、2；指向2，操作3、4，指向4，操作5和null，所以终止循环条件为：curr.next.next == null；

假设当前有偶数个结点[0,1,2,3,4]（0代表虚拟结点），指向0，操作1、2；指向2(⚠️这里是指第二个位置的结点，不是说值为2的结点)，操作3、4，指向4，操作null，所以终止循环条件为：curr.next == null；

当链表为空时，相当于有0个结点，适用于偶数情况；

综上，终止循环条件为 while(curr.next != null && curr.next.next != null)；&&表示只有两个条件都满足（不为空）才会进入循环，交换结点，否则（有一个条件为空）就会终止循环，交换结束；另外，条件的书写顺序不能颠倒，否则curr.next如果为空，curr.next.next会报空指针异常的错误；

2.定义几个临时指针？初始值分别为？

两种情况

情况1：可以定义操作指针curr，初始指向虚拟头结点（对交换结点前一个结点进行操作）；临时指针first，存储两个结点中的第一个结点，初始指向第一个位置的结点，通过curr赋值；临时结点second，存储两个结点中第二个结点，初始指向第二个位置的结点，可通过curr赋值，也可以通过first赋值；临时指针temp，存储两个结点后面的结点，初始值为第三个位置的结点，可通过curr赋值，也可以通过second赋值；具体代码见相关算法题目；

情况2：也可以定义操作指针curr，初始同上；临时指针temp，存储两个结点中第一个结点的位置，

3.交换结点的顺序 

见下图：

如果定义指针是第二种情况（curr和temp），那么顺序只能为：① -> ③ -> ②；

③必须在②前面：如果先②，更改第二个结点的指针方向，那么第三个结点的值就会失去，无法获得，第一个结点就无法更改指针方向；因为temp保存了第一个结点的位置，所以一般先操作结点1，也就是先①；

如果定义指针时第一种情况，无特殊限制，一般为：① -> ② -> ③

三、相关算法题目

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

24. 两两交换链表中的节点 - 力扣（LeetCode）

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode();dummy.next = head;ListNode curr = dummy;ListNode temp;//临时结点 保存两个结点后面的结点ListNode first; //临时结点 保存两个结点中第一个结点ListNode second; //临时结点 保存两个结点中第二个结点while(curr.next != null && curr.next.next != null){//更新first、second、tempfirst = curr.next;second = first.next; //也可以这样更新second和temptemp = second.next;//second = curr.next.next;//temp = curr.next.next.next;//两两交换结点curr.next = second;second.next = first;first.next = temp;//更新curr ⭐️curr = first;}return dummy.next;}
}

具体交换过程如下图：

更新curr时注意，应该为下一组交换结点的前一个结点，也就是第二个位置处的结点，即值为1的结点，也即first

四、错误代码分析

思路：定义一个临时指针temp，用于存储交换结点中第一个结点，定义操作指针curr；

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode();dummy.next = head;ListNode curr = head;ListNode temp = null;while(curr.next != null && curr.next.next != null){temp = curr.next;//保存结点1的值curr.next = curr.next.next;//虚拟头 指向2temp.next = curr.next.next;//1指向3curr.next = temp;//2指向1//更新currcurr = temp.next;}return dummy.next;}
}

错误1：ListNode curr = head;

A：curr初始指向dummy；

错误2： curr.next = temp;//2指向1

A：交换结点的第三步，也是步骤③，结点2更改方向，指向结点1（temp），此时curr.next = 结点2，那么结点2的指针域应该为 curr.next.next，

正确代码为：curr.next.next = temp;

错误3：curr = temp.next;//更新curr

A：temp指向值为1的结点，交换以后，temp指向不变，但是，此时，值为1的结点位置已经发生变化，经过交换，其由第一个位置变成了第二个位置，也就是下一次交换，curr需要指向的位置，可见下图更清晰；

正确代码为：curr = temp;  或者 curr = curr.next.next;