刷题路线来自 ：代码随想录

1. 链表基本操作

707. 设计链表

Leetcode 链接

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：头插
addAtTail(val)：尾插
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：删除链表中的第 index 个节点。

示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

题解：

class Node {int val;Node next;public Node(int val) {this.val = val;}
}
class MyLinkedList {Node head = null;int size = 0;public MyLinkedList() {}// 获取链表中第 index 个节点的值。如果索引无效，则返回-1。public int get(int index) {if (index + 1 > size || index < 0) return -1;Node cur = this.head;for (int i = 0; i < index; i ++) {cur = cur.next;}return cur.val;}// 头插public void addAtHead(int val) {Node node = new Node(val);if (this.head == null) {this.head = node;} else {node.next = this.head;this.head = node;}size++;}// 尾插public void addAtTail(int val) {Node node = new Node(val);if (this.head == null) {this.head = node;} else {Node cur = this.head;while (cur.next != null) {cur = cur.next;}cur.next = node;}size++;}// index 个节点之前添加值为 val的节点。public void addAtIndex(int index, int val) {// index 大于链表长度，节点不插入if (index > size) return;// index小于等于0，则在头部插入节点。if (index <= 0) {addAtHead(val);return;}// 如果 index 等于链表的长度，则该节点将附加到链表的末尾。if (index == size) {addAtTail(val);return;}// 中间位置插入Node node = new Node(val);Node prev = head;// prev 找到 要插入位置前一个结点for (int i = 0; i < index - 1; i ++) {prev = prev.next;}node.next = prev.next;prev.next = node;size++;}// 删除链表中的第 index 个节点。public void deleteAtIndex(int index) {if (index > size - 1 || index < 0) return;if (index == 0) {this.head = this.head.next;size--;return;}if (index == size- 1) {Node prev = this.head;for (int i = 0; i < index- 1; i ++) {prev = prev.next;}prev.next = null;size--;return;}Node prev = head;for (int i = 0; i < index - 1; i ++) {prev = prev.next;}prev.next = prev.next.next;size--;}
}

2. 双指针迭代法

203. 移除链表元素

Leetcode 链接
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

题解：
方法一：

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) return head;ListNode prev = head;ListNode cur = prev.next;while (cur != null) {if (cur.val == val) {// 删除prev.next = cur.next;cur = prev.next; } else {// 不删除prev = cur;cur = prev.next;}}// 因为 cur 从第二个结点开始向后找，头节点还未判断是否为删除结点if (head.val == val) {return head.next;} else {return head;}}
}

方法二：添加虚拟头节点

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) return head;// 虚拟头结点ListNode newHead = new ListNode(-1);newHead.next = head;ListNode prev = newHead;ListNode cur = prev.next;// 迭代while (cur != null) {if (cur.val == val) {prev.next = cur.next;} else {prev = cur;}// 可以放在判断外边cur = prev.next;}return newHead.next;}
}

206. 反转链表

Leetcode 链接
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题解：
注意初值和迭代结束条件

class Solution {public ListNode reverseList(ListNode head) {if (head == null) return null;// 反转后原来的头结点应指向 nullListNode prev = null;ListNode cur = head;// 如果让 curNext 初值为cur.next的话，最后回出现指针越界问题ListNode curNext = cur;while (cur != null) {// 在每轮迭代的开始将 curNext 指向 cur.nextcurNext = cur.next;// 再进行反转cur.next = prev;prev = cur;cur = curNext;// 每轮迭代的结束 cur 是等于 curNext，这样便不会出现指针越界}// 最后一轮迭代 prev 指向原结点的尾，cur 和 curNext 为 nullreturn prev;}
}

24. 两两交换链表中的节点

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]

示例 3：
输入：head = [1]
输出：[1]
题解：
因为链表和前后结点存在关系，所以交换相邻两个结点，影响到的结点除这两个外还有前边和后边各一个，一共4个结点。4个结点之间存在3个 next，画图推出这3个指针之间的迭代顺序即可解题。

class Solution {public ListNode swapPairs(ListNode head) {if (head == null) return null;// 虚拟头结点ListNode newHead = new ListNode(-1);newHead.next = head;ListNode prev = newHead;// 保证有两个结点可以交换才进入循环，若只剩下一个结点，无需交换while (prev.next != null && prev.next.next != null) {// 两个相邻结点ListNode node1 = prev.next;ListNode node2 = node1.next; // 更新3个指针prev.next = node2;node1.next = node2.next;node2.next = node1;// 更新下次迭代的前结点prev = node1;}// 返回真正头结点return newHead.next;}
}

3. 双指针之快慢指针

19. 删除链表的倒数第 N 个结点

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]

题解：
快慢指针以相同速度，相距固定距离开始遍历。使得快指针越界时，慢指针指向要删除的前一个结点，再进行删除结点。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 使用虚拟由结点，不用再去处理只有一个结点的特殊情况ListNode newHead = new ListNode(-1);newHead.next = head;ListNode fast = newHead;ListNode slow = newHead;// 快指针先走到预期位置while (n >= 0 && fast != null) {fast = fast.next;n--;}// 快慢指针一起走，直到快指针越界while (fast != null) {slow = slow.next;fast = fast.next;}// 此时慢指针指向要删除结点的前一个结点，进行删除结点slow.next = slow.next.next;return newHead.next;}
}

160. 相交链表

Leetcode 链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

题解：
若两链表有相交结点，则先遍历完 A结点，再遍历 B结点到相交结点处和先遍历完 B结点，再遍历 A结点到相交结点处经过的结点数相同；
所以分别使用两个结点以相同速度，不同链表开始遍历，遍历完再去遍历另外一个链表，若有相加结点，会相遇，若没有，最后两结点会同时为 null.

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode nodeA = headA;ListNode nodeB = headB;while (nodeA != nodeB) {nodeA = nodeA.next;nodeB = nodeB.next;if (nodeA == null && nodeB == null) {// 如果两链表不相交，且都各自遍历了一遍后此时都为 null，要是不 return 再执行的话就会死循环return null;}if (nodeA == null) {nodeA = headB;}if (nodeB == null) {nodeB = headA;}}return nodeA;}
}

简化：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode nodeA = headA;ListNode nodeB = headB;while (nodeA != nodeB) {nodeA = nodeA == null ? headB : nodeA.next;nodeB = nodeB == null ? headA : nodeB.next;}return nodeA;}
}

141. 环形链表

Leetcode 链接
给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例 1：
输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。
题解：
类比跑步，如果速度不同两人在直道同起点起跑，一定不会相遇；若先是直道后是环道，一定回相遇。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {// 快指针走两步，慢指针走一步fast = fast.next.next;slow = slow.next;// 相遇，返回trueif (fast == slow) return true;}// 走到头(null)了, 没有相遇, 返会falsereturn false;}
}

142. 环形链表 II

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

题解：
快慢指针在环内相遇后，快指针从 head 开始，慢指针从相遇开始，都一次走一步，最后会在入环结点相遇。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {// 第一次相遇：环内相遇fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}// 第二次相遇：入环口return slow;}}return null;}
}

要是想不明白也可以使用哈希表解题：

public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode cur = head;while (cur != null) {if (set.contains(cur)) {// 找到入环结点return cur;} else {// 第一次出现的结点，添加到 set里边set.add(cur);}cur = cur.next;}// 不是环形链表return null;}
}

4. 总结

1. 因为头节点无 prev 结点，很多题都要去单独处理这一情况，而使用虚拟头节点，就不用去单独处理这一情况，方便简洁。
2. 一定注意指针越界的问题，和特殊情况的考虑