网站建设与规划实验心得体会,门户网站建设步骤,wordpress内容函数,教育培训网站模板24.两两交换链表中的节点
文章链接#xff1a;代码随想录 (programmercarl.com)
思路#xff1a;
#xff08;1#xff09;首先如果要处理相邻两个节点的话#xff0c;一定需要操作两个节点的前一个节点才可以#xff0c;因此#xff0c;本题需要设定一个虚拟头节点 …24.两两交换链表中的节点
文章链接代码随想录 (programmercarl.com)
思路
1首先如果要处理相邻两个节点的话一定需要操作两个节点的前一个节点才可以因此本题需要设定一个虚拟头节点
2两两交换节点后原有的链表就断了因此需要对链表的节点进行存储
3基于此应该使用双指针pre指向dummynode虚拟头节点cur指向一开始的头节点
4注意循环条件因为涉及到cur.next.next因此要确保cur和cur.next不为空否则会报错
Java代码
/*** 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) {//先判断特殊情况if(head null){return head;}//定义一个虚拟头节点ListNode dummynode new ListNode();dummynode.next head;//双指针ListNode pre dummynode;ListNode cur head;while(cur ! null cur.next ! null){//保存节点2ListNode temp0 cur.next;//保存节点3ListNode temp1 cur.next.next;//开始指向节点pre.next temp0;temp0.next cur;cur.next temp1;pre cur;cur temp1;}return dummynode.next;}
} 19.删除链表的倒数第N个节点
文章链接代码随想录 (programmercarl.com)
思路单指针和双指针利用对称性都可以操作看代码注释其中双指针代码自己又犯了相同的错误错误如下
1错误1是在最后定位好precur指针位置后直接就写了pre.next cur如果此时链表为[1]那么pre dummynode,cur head此时pre.next cur根本就没有删除
2错误2是在初始化cur位置后开始同时移动pre和cur时的循环条件写错应该写成cur.next ! null不然pre指针会多走一个位置
Java代码单个指针
/*** 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 removeNthFromEnd(ListNode head, int n) {//先判断特殊情况if(head null){return head;}//设置一个虚拟头节点ListNode dummynode new ListNode();dummynode.next head;//定义一个指针ListNode cur dummynode;//统计链表有多少个节点int size 0;while(cur ! null){cur cur.next;size;}//重置指针位置cur dummynode;//找到要删除的节点的前一个节点for(int i 0;i size -1 - n;i){cur cur.next;}//保存删除节点的后一个节点ListNode temp cur.next.next;cur.next temp;return dummynode.next;}
}
Java代码双指针
/*** 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 removeNthFromEnd(ListNode head, int n) {//先判断特殊情况if(head null){return head;}//设置一个虚拟头节点ListNode dummynode new ListNode();dummynode.next head;//双指针ListNode pre dummynode;ListNode cur dummynode;//初始化cur指针位置,对称位置for(int i 0; i n;i){cur cur.next;}//此时开始同时移动pre和cur指针while(cur.next ! null){cur cur.next;pre pre.next;}//此时pre指针指向要删除节点的前一个节点//这里无需判断pre.next是否为空因为cur指针在pre后面,前面的while循环已经判断过了ListNode temp pre.next.next;pre.next temp;return dummynode.next;}
} 面试题 02.07. 链表相交
文章链接代码随想录 (programmercarl.com)
思路
1首先先计算两个链表的长度并且定义两个指针通过移动指针让两个链表对齐开始遍历
2默认定义指针cur1指向长链表指针cur2指向短链表
3从长度一致的地方开始同时遍历
Java代码看代码注释
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//默认cur1指针指向长链表cur2指针指向短链表ListNode cur1 headA;ListNode cur2 headB;//先计算两个链表的长度int lenA 0;int lenB 0;while(cur1 ! null){lenA;cur1 cur1.next;}while(cur2 ! null){lenB;cur2 cur2.next;}//计算完长度后重置一下两个指针cur1 headA;cur2 headB;//因为不知道哪个链表更长因此默认cur1指针指向长链表cur2指针指向短链表//假设lenB比lenA要长if(lenB lenA){//先交换长度int templen lenA;lenA lenB;lenB templen;//再交换两个指针ListNode temp cur1;cur1 cur2;cur2 temp;}//开始对齐指针让长链表的指针往后移动lenA - lenB个步数int gap lenA - lenB;while(gap 0){cur1 cur1.next;gap--;}//此时已经对齐while(cur1 ! null cur2 ! null){//有相交的节点if(cur1 cur2){return cur1;}cur1 cur1.next;cur2 cur2.next;}//没有相交的节点return null;}
} 142.环形链表||
文章链接代码随想录 (programmercarl.com)
思路此题本质上是个数学题定义快慢指针fast指针走过的节点数 slow指针走过的节点数 * 2 类似于数学上的追逐问题想要找到节点首先需要进行画图分析在获取到x z这个信息后就知道了要用双指针来首先找到快慢指针在环中相遇的地方后面在重新定义一个指针index让 index 指针以步长1和slow指针依次遍历两者相遇就找到了环的入口。
Java代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//先判断特殊情况if(head null){return head;}//定义快慢指针快指针步长为1慢指针步长为2ListNode fast head;ListNode slow head;//先找到两个指针相遇的节点位置while(slow ! null fast ! null fast.next ! null){slow slow.next;fast fast.next.next;//找到了两个指针在环内相遇的位置if(slow fast){ListNode index head;while(slow ! null index ! null){//找到了入环的第一个节点if(slow index){return index;}index index.next;slow slow.next;}}}//没有找到返回Nullreturn null;}
}
