前言：今天的题目中，考研时王道数据结构都有相关的题目，有较深的印象，前三题能直接写出来，第四题准备考研时就没理清逻辑，直接看了解析。
24. 两两交换链表中的结点
题目链接：24. 两两交换链表中的结点
链表中结点交换的题目一般在思路上不会太难，要注意的就是在操作的过程中不能断链。
如上图所示，操作过程中需要交换结点2、结点3的位置。个人习惯于先找到待操作节点的前驱节点(如图中p指针），这样无论是对待操作节点的删除还是查找都会非常方便。在图中，只能先操作结点2的next指针指向结点3的next位置，也就是结点4。否则，如果先改变结点1或结点3的next指针，都会导致断链。
代码片段为：
p.next.next = r.next;//Step 1
r.next = p.next;//Step 2
p.next = r;//Step 3
完整代码如下：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0, head);
//虚拟头结点
ListNode p = dummyHead;
ListNode r = p;
//临时指针，记录待操作节点的索引
int count = 1;
while (r.next != null) {
while (r.next != null) {
if (count++ % 3 == 0) break;
r = r.next;
}
if (count % 3 == 2) return dummyHead.next;
//只剩一个节点，无须交换
p.next.next = r.next;
r.next = p.next;
p.next = r;
//交换节点操作
p = r.next;
r = p;
//更新指针位置，进行下一轮交换
}
return dummyHead.next;
}
}
19.删除链表的倒数第N个结点
题目链接：19.删除链表的倒数第N个结点
本题最大的问题在于如何找到倒数的某个结点，不同于数组能够在 O ( 1 ) O(1) O(1)时间查找到任意位置的元素，在链表中需要找到某个结点，需要从链表头开始遍历。运用双指针的话，能够实现遍历一轮找到结点并进行删除。只需要让fast指针先走N步，然后fast和slow指针同时移动，直到fast指向链表尾，此时slow指向的就是倒数N个节点的前驱，便很容易进行删除操作。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0, head);
ListNode p = dummyHead;//slow
ListNode r = dummyHead;//fast
for (int i = 0; i < n; i++) {
r = r.next;//fast指针先前移N步
}
while (r.next != null) {
r = r.next;
p = p.next;
//两指针同步前移
}
p.next = p.next.next;
//结点删除操作
return dummyHead.next;
}
}
面试题 02.07. 链表相交
题目链接：面试题 02.07. 链表相交
首先需要注意的是，链表相交是指针相等而不是数值
val相等。
另外一点，单链表的相交是“Y”型，而非“X”型，即一旦两链表相交在一点，后面便一直公用一点，不会再分开。
提供一种时间复杂度在
O
(
n
+
m
)
O(n + m)
O(n+m)的解题思路。首先计算出两个链表的长度，主要为了得到长度差值diffLength。两指针分别指向两链表头，较长的那条链表指针先走diffLength步（去掉长度差，相当于两条长度相等的链表从头开始寻找），然后两个指针同步前移，如果相交则两指针会在遍历过程中相等，否则在走到链表尾后指针都为空。
代码如下：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode dummyHeadA = new ListNode(0, headA);
ListNode dummyHeadB = new ListNode(0, headB);
ListNode preNodeA = dummyHeadA;
ListNode preNodeB = dummyHeadB;
int diffLength = getLength(dummyHeadA) - getLength(dummyHeadB);
//计算链表长度差
if (diffLength > 0) {
while (diffLength-- != 0) {
preNodeA = preNodeA.next;
}
} else {
while (diffLength++ != 0) {
preNodeB = preNodeB.next;
}
}
//消除长度差
while (preNodeA != preNodeB && preNodeA != null) {
preNodeA = preNodeA.next;
preNodeB = preNodeB.next;
}
return preNodeA;
}
//返回链表长度
public int getLength(ListNode dummyHead) {
int length = 0;
while (dummyHead.next != null) {
dummyHead = dummyHead.next;
length++;
}
return length;
}
}
142.环形链表II
题目链接：142.环形链表II
参考文章链接：代码随想录_142.环形链表II
(强烈建议参考代码随想录中卡哥对本题的解析，非常透彻）
下面进行分析，定义快慢指针fast和slow，都从头结点出发，fast指针每次前移两个节点，slow节点每次前移一个节点。这种情况下，如果链表存在环，两指针一定会相遇。
具体解释：为什么一定会在环中相遇，而不是会错开呢？首先能够知道，两个指针如果能相遇，一定是在环中相遇。且是fast指针追上slow指针。
不妨来看下图中几种情况
-
情形一
相隔一点时，下一个状态就会相遇
-
情形二
相隔两点时，下一个状态变为情形一所示。
-
情形三
相隔三点时，下一个状态，变为情形二所示。
相对于slow来说，fast是一个节点一个节点的靠近slow的（fast指针相对于slow指针的运动速度为1，理解为slow在fast前n步，slow相对静止而fast一步一步去追slow），所以fast一定可以和slow重合。
证实了一定会相遇这一点之后，下面来找到环的入口。
借用代码随想录中卡哥的一张图，假设从头结点到环形的节点数为x。 环形入口到两指针相遇的节点数为y。 从相遇节点再到环形入口节点节点数为z，环形总结点数为y + z。
相遇时slow指针走的总结点长度为x + y，而在两指针相遇之前，fast指针已经在环中走了n圈，所以fast指针走过的总结点长度x + y + n (y + z)，加上fast指针的速度是slow指针的两倍这一条件，可以得到如下等式：
2 (x + y) = x + y + n (y + z)
我们的目的是找出入口节点的位置，也就是x的长度，所以把x移到一边，对等式进行化简:
x = n (y + z) - y = (n - 1)(y + z) + z
n一定是大于等于1的，不妨先假设 n = 1, 此时x = z，也就可以理解为只需要让两个指针index1、index2分别从头结点和 fast指针与slow指针相遇的节点处 出发，这两个指针相遇处即为环形入口节点。
如果n大于1，只是相当于index2相遇前在环里多转了几圈，最终仍是在环形入口处相遇，不会影响结果。
代码如下：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
//快慢指针相遇
ListNode index1 = head;
ListNode index2 = fast;
//分别指向头结点和相遇点
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;//相遇即入口
}
}
return null;//无环返回null
}
}