代码随想录算法训练四天任务：
● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交 （同160）
● 142.环形链表II
● 总结
24. 两两交换链表中的节点
方法一 ：迭代
更直观的表示：
交换步骤：
结论
我们要交换两个结点， 需要保存 两个结点之前的和之后的结点
因为链表是单向的， 那么 之前 结点我们需要使用一个临时变量保存。
为什么呢？ 如果当前指针遍历到1结点，此时不保存上一个结点，我们就无法“回头”找到 它了.之后结点可以通过 2->next 得到，只要保证 1->3 连接建立之前， 2的next值不被改就可以保证链表不会断。因为2的next值提前被改了，那么我们就找不到3节点了。
基于以上结论，我们可以给原链表加一个头结点，并且定义三个指针 f/s/t(first/second/third)，分别指向头结点、 第 1 个结点、第 2 个结点。（在code 中使用了prevNode, swapLeft, swapRight 来表示）
结点 1 和 2交换完成之后， 指针后移2位（代码层面就是保证不出现空指针异常或者段错误） ，然后交换 3 和 4 结点。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
// prevNode 遍历链表时用
ListNode prevNode = dummyNode;
while(prevNode.next != null && prevNode.next.next != null){
ListNode swapLeft = prevNode.next; //left node of swap pair
ListNode swapRight = swapLeft.next; //right node of swap pair
ListNode temp = swapRight.next;
//swap
prevNode.next = swapRight;
swapRight.next = swapLeft;
swapLeft.next = temp;
//如果不定义temp变量则swap步骤需改变为：
// prevNode.next = swapRight;
// swapLeft.next = swapRight.next;
// swapRight.next = swapLeft;、
//标杆位后移2位
prevNode = prevNode.next.next;
}
return dummyNode.next;
}
}
时间复杂度： 整个链表需要遍历一遍，所以算法时间复杂度的上限是 O(n)
空间复杂度： 不管链表有多长，运行算法需要额外开辟的空间总是常数级的，算法的空间复杂度是O(1)
方法二 递归
递归终止条件： 当前节点或下一节点为null
class Solution {
public ListNode swapPairs(ListNode head) {
////递归的终止条件
if(head == null || head.next == null) return head;
//假设链表是 1->2->3->4
//这句就先保存节点2
temp = head.next;
//继续递归，处理节点3->4
//当递归结束返回后，就变成了4->3
//于是head节点就指向了4，变成1->4->3
head.next = swapPairs(temp.next);
//将2节点指向1, 2此时成为第一个节点
temp.next = head;
return temp;
}
}
时间复杂度： O(n)
空间复杂度： 递归栈O(n)
19. 删除链表的倒数第N个节点
方法一 2 passes
第一遍循环找到链表长度len， 得到需要被移除节点位置
第二遍循环到节点 , 移除此节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode curr = head;
int length = 0;
if(head == null) return head;
//第一遍循环找到链表长度len， 得到需要被移除节点位置 length - n
while(curr != null){
curr = curr.next;
length++;
}
int delPosition = length - n;
//第二遍循环到delPosition节点, 移除此节点
curr = dummyHead;
while(delPosition > 0){
curr = curr.next;
delPosition--;
}
curr.next = curr.next.next;
return dummyHead.next;
}
}
时间复杂度： 遍历两遍 O(n)
空间复杂度： O(1)
方法二 快慢指针 1 pass
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//定义fast指针和slow指针，初始值为虚拟头结点
ListNode fast = dummyHead;
ListNode slow = dummyHead;
//fast首先走n + 1步,
//只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
for(int i = 0; i < n + 1; i++){
fast = fast.next;
}
//fast和slow同时移动，直到fast指向末尾
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//删除slow指向的下一个节点
slow.next = slow.next.next;
return dummyHead.next;
}
}
时间复杂度： 遍历一遍 O(n)
空间复杂度： O(1)
面试题 02.07 链表相交 （同160）
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null
方法一 HashSet
思路和算法
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果当前节点不在哈希集合中，则继续遍历下一个节点；
如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet visited = new HashSet<ListNode>();
ListNode nodeA = headA;
while(nodeA != null){
visited.add(nodeA);
nodeA = nodeA.next;
}
ListNode nodeB = headB;
while(nodeB != null){
if(visited.contains(nodeB)) return nodeB;
nodeB = nodeB.next;
}
//两个链表不相交，返回 null
return null;
}
}
时间复杂度 O(m + n)
空间复杂度 O(m) m为链表A 长度
方法二 双指针
用双指针将时间复杂度降低为O(1)
思路：
走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
如果两个链表相交，则相交后的长度相同
设A的长度为a+c，B的长度为b+c；其中c为A、B的公共部分；
若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在c的起点相遇。若不相交，a +b = b+a 。因此相遇处是NULL
具体解释：
假设headA, headB 长度分别为m,n。 非公共部分长度分别为a, b; 公共部分长度为c
情况一： 相交
如果a=b, 则指针pA,pB会同时达到c,pA = pB = c的开始节点， 返回相交节点；
如果a != b,则pA,pB会分别遍历完headA, headB。 然后pA移到headB的头节点，pB移到headA的头节点， 两指针继续分别移动。在pA移动了a+c+b次，pB移动了b+c+a次后，到达公共部分c
情况二： 不相交
当m=n， pA,pB同时到达链表尾部，同时为null,返回null
当m != n, pA, pB 会各自遍历完两个headA, headB 两个链表，pA移动m+n次，pB移动n+m次，同时变为null, 返回null
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//设A的长度为a+c，B的长度为b+c；其中c为A、B的公共部分；
// 拼接AB、BA：A+B=a+c+b+c B+A=b+c+a+c；由于a+c+b=b+c+a，
//因此二者必定在c的起始点处相遇
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while(pA != pB){
//遍历完链表headA,再遍历链表headB
pA = (pA == null ? headB : pA.next);
//遍历完链表headB,再遍历链表headA
pB = (pB == null ? headA : pB.next);
}
return pA;
}
}
时间复杂度 O(m + n)
空间复杂度 O(1)
双指针相似思路：
并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点.否则循环退出返回空指针。
142. 环形链表II
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
方法一： 哈希set
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set visited = new HashSet<ListNode>();
while(pos != null){
if(visited.contains(pos)) return pos;
visited.add(pos);
pos = pos.next;
}
return null;
}
}
时间复杂度： O(n)
空间复杂度： O(n)
