代码随想录训练营第4天，链表也要收尾啦。
24. 两两交换链表中的节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
解法一：设置虚拟头节点
基本思路：建议画图
- 首先设置虚拟头结点 dummyHead，并将其指向原本的头结点，且为当前节点 cur
进入循环，终止条件为头结点后面不存在两个节点 - 通过改变指针的方向来交换头结点后面两个点node1，node2的位置
- cur.next = node2
- node2.next = node1;
- node1.next = node2.next;
- 更新 cur 的位置，往后移一位
class Solution {
public ListNode swapPairs(ListNode head) {
//创建虚拟头节点，将虚拟头节点设成当前节点cur
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode cur = dummyHead;
while(cur.next != null && cur.next.next != null){
ListNode node1 = cur.next;
ListNode node2 = cur.next.next;
//三部曲,注意顺序
cur.next = node2;
node1.next = node2.next;
node2.next = node1;
cur = node1;
}
return dummyHead.next;
}
}
解法二：迭代法 （稍后更新）
19.删除链表的倒数第N个节点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
解法一：快慢指针+虚拟头节点
主旨：设置快慢指针，想让快指针走n步，然后让快慢指针同时走，等快指针指向null的时候，删除慢指针所指的点；
1.设置虚拟头，初始化快慢指针，都指向虚拟头
2.快指针走/n+1/步，为的是让慢指针指向要删的前一个节点，方便链表操作
3.快慢指针同时走，快指针指向null时停
4.慢指针删除它目前位置的下一个节点
5.返回头节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//初始设置，双指针法
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
//先让fast指针跑n个位置
for(int i=0; i<n;i++){
fast = fast.next;
}
//当fast 在n 位上时，slow 和 fast 同时往前，直到fast走到底
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
解法一：常规解法
基本思路：
找出两个链表交点的指针；比较指针，不是比较值
题目为了方便比较，默认数值相同则指针就相同！
1.设置currA，currB两指针，分别指向两个链表的表头；
2.计算A，B长度；将长的链表设为A，并且移动currA到B表头的位置；让currA和currB处于同一起跑线
3.currA，currB同时移动，如果指针相同，则返回currA；没有则返回null。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//初始化
ListNode currA = headA;
ListNode currB = headB;
int lenA = 0;
int lenB = 0;
//计算两个链表的长度
while(currA != null){
lenA++;
currA = currA.next;
}
while(currB != null){
lenB++;
currB = currB.next;
}
//将当前节点重新初始化头节点
currA = headA;
currB = headB;
//确保A链表是长的那个
if(lenB > lenA){
int tempL = lenB;
lenB = lenA;
lenA = tempL;
ListNode tempN = currB;
currB = currA;
currA = tempN;
}
int gap = lenA - lenB;
//当链表A被遍历到和B链表一样的位置时，currA 和 currB 齐头并进
for (int i = 0; i < gap;i++){
currA = currA.next;
}
while(currA != null){
if (currA == currB){
return currA;
}
currA = currA.next;
currB = currB.next;
}
return null;
}
}
解法二：高级解法
解题思路：把两条链表相加，成为一条长的链表
headA先遍历表A再去遍历表B；
headB先遍历表B再去遍历表A；
当A，B重合时：
·如果有公共节点，则停在公共节点上；
·如果没有公共节点，两点只会都停在null上
因此，返回A即可；
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A != B){
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;
}
}
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
解法一：快慢指针
基本思路：
- 设置 fast 和 slow 两个指针，开始遍历链表；初始化都在 head 节点。
- fast 每次走两步，slow 每次走一步，如果存在环，则 fast 和 slow 必定在环内相遇；如果不存在环，则返回 null
- 当 fast 和 slow 相遇时，将 index1 设为 fast 的位置，将 index2 设为 head 的位置；每次 index1 和 index2 都走一步，最终 index1 和 index2 会在环入口相遇。则返回 index1.
具体证明过程，见https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
public class Solution {
public ListNode detectCycle(ListNode head) {
// if (head == null || head.next == null){
// return null;
// }
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (fast == slow){
ListNode index1 = fast;
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
