网站页面改版,石家庄房产信息网,正在备案怎么建网站,料远若近网站建设目录
一、链表理论基础
二、思路及易错点
易错点
三、相关算法题目
四、错误代码分析 一、链表理论基础
代码随想录 (programmercarl.com)
二、思路及易错点
该题使用虚拟头结点正常进行模拟即可#xff0c;有两个关键点#xff0c;一是循环何时终止#xff1f;终止…目录
一、链表理论基础
二、思路及易错点
易错点
三、相关算法题目
四、错误代码分析 一、链表理论基础
代码随想录 (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;}
}
错误1ListNode curr head;
Acurr初始指向dummy
错误2 curr.next temp;//2指向1
A交换结点的第三步也是步骤③结点2更改方向指向结点1temp此时curr.next 结点2那么结点2的指针域应该为 curr.next.next
正确代码为curr.next.next temp;
错误3curr temp.next;//更新curr
Atemp指向值为1的结点交换以后temp指向不变但是此时值为1的结点位置已经发生变化经过交换其由第一个位置变成了第二个位置也就是下一次交换curr需要指向的位置可见下图更清晰
正确代码为curr temp; 或者 curr curr.next.next;
