leetcode-04-[24]两两交换链表中的节点[19]删除链表的倒数第N个节点[160]相交链表[142]环形链表II

一、[24]两两交换链表中的节点

重点：暂存节点

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead=new ListNode(-1);dummyHead.next=head;ListNode pre=dummyHead;//重点：存节点while(pre.next!=null&&pre.next.next!=null){ListNode tmp=pre.next;ListNode tmp1=pre.next.next.next;pre.next=pre.next.next;//1、注意一下pre.next.next=tmp;//2、注意一下tmp.next=tmp1;pre=pre.next.next;}return dummyHead.next;}
}

二、[19]删除链表的倒数第N个节点

重点：
1、为啥要让快指针先行？
快指针先行n步，这样快慢指针之间形成了一段长度为n的窗口，之后快慢指针同步向前相当于保持窗口长度不变。这样当快指针到达了末尾指向NULL，另一端的慢指针距离末尾的长度是n，自然就是指向倒数第n个位置了。
2、为啥快指针先行了n+1步？（相当于窗口大小 n+1）
由于单链表中的next指针指向的是下一个节点，想要删除倒数第n个节点，自然要将操作指针慢指针指向倒数第n+1个节点，这样才能进行删除操作。

x-1+1=n+1(1 为第一个节点，即dummyHead)

x=n+1(即相对于第一个节点，前进n+1步)
3、虚拟头节点dummyHead的作用是？
如果单链表中要删除的节点是头节点，这个头节点正好是dummyHead的下一个节点，如此即可统一起来删除操作而不必单独考虑。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//快慢指针 窗口为n+1ListNode dummyHead=new ListNode(-1);dummyHead.next=head;ListNode slow=dummyHead;ListNode fast=dummyHead;for(int i=0;i<n+1;i++){fast=fast.next;}while(fast!=null){slow=slow.next;fast=fast.next;}slow.next=slow.next.next;return dummyHead.next;}
}

三、[160]相交链表

重点：让两个链表一样长

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1=headA;ListNode p2=headB;//不存在相交节点，则null=nullwhile(p1!=p2){if(p1==null){p1=headB;}else{p1=p1.next;}if(p2==null){p2=headA;}else{p2=p2.next;}}return p1;}
}

四、[142]环形链表II

建议先写[141]环形链表

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow=head;ListNode fast=head;//1、判断条件while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow){ListNode index1=fast;ListNode index2=head;//2、此处为while循环while(index1!=index2){index1=index1.next;index2=index2.next;}return index1;}}return null;}
}

引自代码随想录网站：代码随想录