深圳网站建设索q.479185700爱站网 关键词挖掘工具

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是在最后定位好pre，cur指针位置后，直接就写了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;}
}