24. 两两交换链表中的节点
考察链表的基本操作，操作当前节点，获取上一个节点，保存下一个节点。
class Solution {
public ListNode swapPairs(ListNode head) {
// 创建虚拟头节点，因为可能会修改头节点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
// 保存上一个节点的引用
ListNode prev = dummyHead;
ListNode curr = head;
while (curr != null && curr.next != null) {
// 保存下一对的起始节点的引用
// 下次循环要从这个引用开始
ListNode tmp = curr.next.next;
// 反转，交换顺序也无妨
prev.next = curr.next;
curr.next.next = curr;
// 把断开的节点再连上
curr.next = tmp;
// 前进
prev = curr;
curr = curr.next;
}
return dummyHead.next;
}
}看图：
由迭代法可知递归法：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
// 开始递归处理
helper(head, dummyHead);
// 返回链表反转后的头节点
return dummyHead.next;
}
public void helper(ListNode curr, ListNode prev) {
// 没有节点，或者只有一个节点，无需反转，不做处理
if (curr == null || curr.next == null) return;
// 保存下一对起始节点的引用
ListNode tmp = curr.next.next;
// 开始反转
prev.next = curr.next;
curr.next.next = curr;
// 记得连接，否则就断了
curr.next = tmp;
// 递归处理下一对
helper(curr.next, curr);
}
}19. 删除链表的倒数第 N 个结点
知识点：
- 单链表删除节点，需要知道前一个节点。
- 倒数第 n 个节点，就是正数第 size - n + 1 个节点。
- 从第 i 个节点遍历，到达第 j 个节点，需要前进 j - i 步。
第一种解法：可以从头开始遍历，第 size - n + 1 个节点就是要删除的节点（循环 size - n 次），但是首先得知道链表的长度。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
// 计算长度
int len = 0;
ListNode curr = head;
while (curr != null) {
curr = curr.next;
len++;
}
// 前进到第 size - n + 1 个节点，得循环 size - n 次
n = len - n;
curr = head;
ListNode prev = dummyHead;
while (n > 0) {
prev = curr;
curr = curr.next;
n--;
}
if (curr != null) {
prev.next = curr.next;
}
return dummyHead.next;
}
}第二种解法：我们可以先定义两个指针，一个指针从 head 开始，先前进 n 步，然后另一个节点也从 head 开始，然后两个节点同时前进，当第一个节点到达链表末尾的时候，第二个节点正好到达第 n 个节点，但是要删除第 n 个节点，所以要获取前一个节点，即第 n - 1 个节点，因此第二个节点得从虚拟头节点开始。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 因为要删除节点，所以用虚拟头节点统一操作
ListNode dummyHead = new ListNode();
dummyHead.next = head;
// prev 从 dummyHead 开始，表示要删除节点的前一个节点
ListNode prev = dummyHead;
// curr 从 head 开始遍历链表
ListNode curr = head;
// curr 前进 n 步
while (curr != null && n > 0) {
curr = curr.next;
n--;
}
// prev 和 curr 同时前进，直到 curr 为 null
while (curr != null) {
prev = prev.next;
curr = curr.next;
}
// 删除第 n 个节点
prev.next = prev.next.next;
return dummyHead.next;
}
}160. 链表相交
链表相交即两个链表从某个节点开始，往后都相等。根据题目的图可以想到，将两个链表尾部对齐，让两个链表从同一长度开始遍历（让较长的链表前进几步），如果碰到某个节点相同，那么这就是交点，否则没有交点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode currA = headA;
ListNode currB = headB;
// 先计算长度
while (currA != null) {
currA = currA.next;
lenA++;
}
while (currB != null) {
currB = currB.next;
lenB++;
}
currA = headA;
currB = headB;
// 长度长的，往前走几步
if (lenA > lenB) {
int x = lenA - lenB;
while (x > 0) {
currA = currA.next;
x--;
}
} else {
int x = lenB - lenA;
while (x > 0) {
currB = currB.next;
x--;
}
}
// 从同一长度开始遍历
while (currA != null && currB != null && currA != currB) {
currA = currA.next;
currB = currB.next;
}
// 循环结束，如果 currA == currB，那么都指向交点，返回哪个都行
// 如果有一个是 null，那说明不相交
return currA;
}
}142. 环形链表 II
Floyd 的环路查找算法：使用快慢指针，慢指针一次移动一格，快指针一次移动两格，如果没有环，则快指针率先到达 null，循环结束；如果有环，则快慢指针一定会相遇（?），且快指针走的距离是慢指针的两倍。当快慢指针相遇时，将慢指针重置到 head，快指针还在相遇点，然后二者同时前进，一次走一格，再次相遇时即为环的入口。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// 找环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
// 没环
if (fast == null || fast.next == null) return null;
// 有环，找入口点
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}