day4 | 24.两两交换链表中的结点、19.删除链表的倒数第N个结点、面试题：链表相交、142.环形链表

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路：

 1 class Solution {
 2     public ListNode swapPairs(ListNode head) {
 3         //创建虚拟头结点，把头结点看作普通结点来处理
 4         ListNode dummy = new ListNode(0);
 5         dummy.next = head;
 6         ListNode curr = dummy;
 7         while(curr.next!=null && curr.next.next!=null){
 8             //创建结点用于存储结点
 9             ListNode temp = curr.next;
10             ListNode temp1 = curr.next.next;
11             //两两交换链表中的结点
12             curr.next = curr.next.next;
13             curr.next.next = temp;
14             curr.next.next.next = temp1;
15             //完成交换后curr向后移两位
16             curr=curr.next.next;
17         }
18         return dummy.next;
19     }
20 }

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路：使用双指针

 1 class Solution {
 2     public ListNode removeNthFromEnd(ListNode head, int n) {
 3         //创建虚拟头结点
 4         ListNode dummy = new ListNode(0);
 5         dummy.next=head;
 6         ListNode del = dummy;
 7         ListNode q=del;
 8         for(int i=0 ; i<n;i++) {
 9             q=q.next;
10             }
11         while(q.next!=null){
12             q=q.next;
13             del=del.next;
14         }
15         //此时要删除的元素为 del.next
16         del.next=del.next.next;
17         return dummy.next;
18     }
19 }

题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

解题思路：

求出两个链表的长度，并求出两个链表长度的差值，然后让currA移动到和currB末尾对齐的位置。

 1 public class Solution {
 2     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 3         ListNode curA=headA;
 4         ListNode curB=headB;
 5         int lenA=0,lenB=0;
 6         //求链表长度
 7         while(curA.next!=null){
 8             curA=curA.next;
 9             lenA++;
10         }
11         while(curB.next!=null){
12             curB=curB.next;
13             lenB++;
14         }
15         //确保ListA是长链
16         if(lenB > lenA){
17             int templen = lenA;
18             lenA = lenB;
19             lenB = templen;
20             //swap(lenA,lenB)
21             ListNode tempNode = curA;
22             curA = curB;
23             curB = tempNode;
24             //swap(curA,curB)
25         }
26         //移动curA指针至对齐ListB末尾的位置
27         int gap = lenA-lenB;
28         while(gap-->0) {
29             curA = curA.next;
30             }
31         //判断链表是否相交
32         while(curA!=null){
33             if(curA==curB){//判断两个链表是否相交，可以直接比较他们的地址是否相等
34                 return curA;
35             }
36             curA=curA.next;
37             curB=curB.next;
38         }
39         return null;
40     }
41 }

题目链接：142. 环形链表 II - 力扣（LeetCode）

题目描述：

　　给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

　　如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

解题思路：

定义快慢指针，参考文章代码随想录 (programmercarl.com)

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         ListNode slow = head;
 4         ListNode fast = head;
 5         while(fast!=null && fast.next!=null){
 6             //慢指针每次走一步，快指针每次走两步
 7             slow = slow.next;
 8             fast = fast.next.next;
 9             if(fast==slow){
10                 //快指针与慢指针相遇，说明存在环
11                 ListNode Index1=fast;
12                 ListNode Index2=head;
13                 while(Index1!=Index2){
14                     //利用等式x=z，找到环的入口
15                     Index1=Index1.next;
16                     Index2=Index2.next;
17                 }
18                 return Index1;
19             }            
20         }
21         return null;
22     }
23 }