24. 两两交换链表中的节点
题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
注意点：使用虚拟头节点，cur一开始指向dummy head
当链表节点为奇数时，当current.next.next为空时，遍历停止
当链表节点为偶数时，当current.next为空时，遍历停止
所以while(cur.next != null && cur.next.next != null)，就会一直遍历下去
交换顺序的代码：比如，dummy head应该指向第2个节点，第2个节点再指向第1个节点，1再指向3……所以要:
- 注意：
while循环的终止条件
保存节点1和节点3
最后的cur指针移动到cur.next.next（下一组准备交换的前一个节点）
/**
* 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);
dummyHead.next = head;
ListNode cur = dummyHead;
while(cur.next != null && cur.next.next != null){
ListNode temp = cur.next;
ListNode temp1 = cur.next.next.next;
cur.next = cur.next.next;
cur.next.next = temp;
cur.next.next.next = temp1;
cur = cur.next.next;
}
return dummyHead.next;
}
}
19.删除链表的倒数第N个节点
注意：
双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点
快指针先行n步，这样快慢指针之间形成了一段长度为n的窗口，之后快慢指针同步向前相当于保持窗口长度不变。这样当快指针到达了末尾指向NULL，另一端的慢指针距离末尾的长度是n，自然就是指向倒数第n个位置了。
快指针先行了n+1步？
由于单链表中的next指针指向的是下一个节点，想要删除倒数第n个节点，自然要将操作指针慢指针指向倒数第n+1个节点，这样才能进行删除操作。
pseudocode
fast = dummyHead;
slow = dummyHead;
while(n--&& fast != null){
fast = fast.next
}
fast=fast.next //快指针要走n+1步
//java中就是for(i=0;i<=n;i++)
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//删除节点
slow.next = slow.next.next
//返回链表头节点
return dummyHead.next
/**
* 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) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
// 这里实际上走了n+1步
for(int i = 0; i <= n; i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
if(slow.next != null){
slow.next = slow.next.next;
}
return dummyHead.next;
}
}
面试题 02.07. 链表相交
/**
* 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) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while(curA != null){
lenA ++;
curA = curA.next;
}
while(curB != null){
lenB ++;
curB = curB.next;
}
curA = headA;
curB = headB;
if(lenB > lenA){
int temp = lenA;
lenA = lenB;
lenB = temp;
ListNode tempNode = curA;
curA = curB;
curB = tempNode;
}
int gap = lenA - lenB;
// or while(gap-- > 0)
for(int i = 0; i < gap; i++){
curA = curA.next;
}
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
注意 数值相同，不代表指针相同。
思路：求出链表的长度和长度差值，保证链表A是较长的那一个。让curA移动到和curB指针对齐的位置。向后移动指针，当curA==curB时，就找到相交的位置。
142.环形链表II
算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
/**
* 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) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){ // 注意这里在while循环内
ListNode index1 = fast;
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index2;
}
}
return null;
}
}
注意：fast每次要比slow移动快一步
当fast追及到slow时，从head到入口和从两个指针的交点到入口长度相等。
总结
注意使用到的技巧：
- 虚拟头节点
- 改变指针指向时，要先改变后面的指向，再改变前面的。
- 快慢指针
