24. 两两交换链表中的节点
题目链接: 24. 两两交换链表中的节点 - 力扣（LeetCode）
题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
思路
- 使用虚拟头结点，用于处理头结点交换的问题。
- 画图，理清处理顺序。
截取自代码随想录的思路图，可以参考一下。
代码
1 class Solution {
2 public ListNode swapPairs(ListNode head) {
3 ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
4 dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
5 ListNode cur = dumyhead;
6 ListNode temp; // 临时节点，保存两个节点后面的节点
7 ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
8 ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
9 while (cur.next != null && cur.next.next != null) {
10 temp = cur.next.next.next;
11 firstnode = cur.next;
12 secondnode = cur.next.next;
13 cur.next = secondnode; // 步骤一
14 secondnode.next = firstnode; // 步骤二
15 firstnode.next = temp; // 步骤三
16 cur = firstnode; // cur移动，准备下一轮交换
17 }
18 return dumyhead.next;
19 }
20 }
递归版本
19.删除链表的倒数第N个节点
题目链接: Loading Question... - 力扣（LeetCode）
题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路
应用双指针，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
关于处理头节点的问题，可以继续采用虚拟头节点。
代码
1 class Solution {
2 public ListNode removeNthFromEnd(ListNode head, int n) {
3 ListNode dummyHead = new ListNode(-1,head); // 定义虚拟头节点
4 ListNode fast = dummyHead;
5 ListNode slow = dummyHead;
6
7 // 让 fast 先走 n 步
8 while(n-- > 0){
9 fast = fast.next;
10 }
11
12 // 让 fast 和 slow 同时走直至 fast下一个节点为null 结束
13 // 此时 slow 就为要删除的节点的前一个
14 while(fast.next != null){
15 slow = slow.next;
16 fast = fast.next;
17 }
18 slow.next = slow.next.next; // 删除操作
19 return dummyHead.next;
20 }
21 }
面试题 02.07. 链表相交
题目链接: 面试题 02.07. 链表相交 - 力扣（LeetCode）
题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
思路
先求出两个链表的长度，在求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置。
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
如果循环退出，则返回null，说明没有交点
代码
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 while (curA != null) { // 求链表A的长度
7 lenA++;
8 curA = curA.next;
9 }
10 while (curB != null) { // 求链表B的长度
11 lenB++;
12 curB = curB.next;
13 }
14 curA = headA;
15 curB = headB;
16 // 让curA为最长链表的头，lenA为其长度
17 if (lenB > lenA) {
18 //1. swap (lenA, lenB);
19 int tmpLen = lenA;
20 lenA = lenB;
21 lenB = tmpLen;
22 //2. swap (curA, curB);
23 ListNode tmpNode = curA;
24 curA = curB;
25 curB = tmpNode;
26 }
27 // 求长度差
28 int gap = lenA - lenB;
29 // 让curA和curB在同一起点上（末尾位置对齐）
30 while (gap-- > 0) {
31 curA = curA.next;
32 }
33 // 遍历curA 和 curB，遇到相同则直接返回
34 while (curA != null) {
35 if (curA == curB) {
36 return curA;
37 }
38 curA = curA.next;
39 curB = curB.next;
40 }
41 return null;
42 }
43 }
142.环形链表II
题目链接: 142. 环形链表 II - 力扣（LeetCode）
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
思路
该题一共有两问：判断是否存在环 和 确定环的起点。
判断是否存在环：可以采用快慢指针的方式，快指针一次走两个节点，慢指针一次走一个节点(相对于slow来说，fast是一个节点一个节点的靠近slow的)。如果链表是环形的，快慢指针必然会在环内相遇(有可能是环的起始点，有可能是环内的某一点，且在慢指针还在第一圈的时候就相遇了）。
关键点在于如何确定环的起始点。需要运用一点数学知识。
如图，设相遇时慢指针走了 x + y,快指针走了 x + y + n (y + z)。由快慢指针的定义得： 2(x + y) = x + y + n(y + z) => x = n(y + z) - y。
再从 n(y + z) 中提出一个 （y+z）来，整理公式之后为如下公式:x = (n - 1)(y + z) + z (注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针）。
如果n=1,那么可得 x = z；通过这个等式就知道找到环的节点的方法。令index1等于快慢指针相遇处，index2等于head；当index1=index2的时候，代表这两个指针相遇到了环的入口处。即使n>1，那么index2走了n-1圈后，再走z步也会和index2相遇在环的入口处。
代码
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 slow = slow.next;
7 fast = fast.next.next;
8 if (slow == fast) {// 有环
9 ListNode index1 = fast;
10 ListNode index2 = head;
11 // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
12 while (index1 != index2) {
13 index1 = index1.next;
14 index2 = index2.next;
15 }
16 return index1;
17 }
18 }
19 return null;
20 }
21 }
标签：ListNode,随想录,fast,next,链表,curA,节点 From： https://www.cnblogs.com/xpp3/p/17096906.html