1.删除排序链表的重复元素（82-中）
题目描述：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。返回同样按升序排列的结果链表。
示例：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
思路：本题通过递归和迭代实现，高频面试题。
法1：递归（自上而下）：
- 递归函数：删除全部重复节点
- 终止条件：
head == null || head.next == null（没有元素或只有一个元素，直接返回） - 递归逻辑：比较当前值和下一个节点的值，值相同，记录第一个重复的元素，找到下一个值不同的元素继续递归；值不同，直接连接，继续下一个节点。
法2：迭代实现，由于链表元素是升序的，所以我们进行一次遍历，就能删除链表中的重复元素。具体如下：
- 如果cur.next与cur.next.next对应的元素不同，那么直接移动cur指针
- 否则，记录cur.next这个值为x，从cur.next开始，将值等于x节点全部删除。注意：递归中我们是直接舍弃重复元素（从不重复的元素开始），这里重复元素应该从头结点开始遍历（虚拟节点下一个节点）！
注意：由于链表的头节点也可能被删除，所以我们可以使用一个虚拟节点指向链表的头结点（这与83题不同，节点元素唯一）
// 代码1：递归 public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } if (head.val == head.next.val) { ListNode temp = head.next; while (temp != null && head.val == temp.val) { // 删除重复节点 temp = temp.next; } return deleteDuplicates(temp); } else { head.next = deleteDuplicates(head.next); } return head; } // 代码2：迭代 public ListNode deleteDuplicates(ListNode head) { if (head == null) { return head; } ListNode dummyHead = new ListNode(); dummyHead.next = head; ListNode cur = dummyHead; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int x = cur.next.val; while (cur.next != null && cur.next.val == x) { // 删除重复节点 cur.next = cur.next.next; } } else { cur = cur.next; } } return dummyHead.next; }
2.删除排序链表的重复元素（83-易）
题目描述：删除一个链表中所有重复的元素，保证出现元素的唯一性。与上一题不同的是本题相同元素保留1个。注意链表已经排序。
示例：
输入: 1->1->2 输出: 1->2
思路：本题通过递归和迭代实现。
法1：递归（自下而上）：
- 递归函数：找到不重复（元素唯一）链表头结点
- 终止条件：
head == null || head.next == null（没有元素或只有一个元素） - 递归逻辑：比较当前值和下一个节点的值，若相同则返回当前节点的下一个节点，否则返回当前节点。
法2：迭代实现：定义两个指针，找到重复元素的区间：
- pre指针记录重复节点区间的开始；
- cur指针记录重复节点区间的结尾，cur.next是下一个不重复的元素；
- 更新pre和cur（保证相邻节点值不同）。
// 代码1：递归 public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); //节点连接 return head.val == head.next.val ? head.next : head; } // 代码2：迭代 public ListNode deleteDuplicates(ListNode head) { ListNode cur = head, pre = head; while (cur != null) { while (cur.next != null && cur.val == cur.next.val) { cur = cur.next; } pre.next = cur.next; cur = cur.next; pre = cur; } return head; }
3.删除链表元素（203-易/剑指18）
题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
思路：本题通过递归和迭代实现。
法1：递归（自下向上，类似T83）：
- 递归函数：获取不含指定元素的链表
- 终止条件：
head == null（没有元素）！ - 递归逻辑：比较当前节点是不是要删除的节点。如果是继续递归下一个节点，否则进行连接，并返回。
法2：迭代实现：
- 遍历链表，如果等于给定值，删除（重新连接）；否则，更新cur指针。
- 注意迭代退出的条件，因为本题不是和当前节点的下一个节点进行比较，而是给定了目标值，所以只需要保证cur.next != null即可。
ps：因为头结点可能被删除，所以我们创建虚拟节点，保证每个节点都有前驱节点，这样不用单独考虑删除头结点的情况。（这一点与T82相同）
// 代码1：递归 public ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } // 代码2：迭代 public ListNode removeElements(ListNode head, int val) { if (head == null) return head; ListNode dummyHead = new ListNode(val - 1); dummyHead.next = head; ListNode cur = dummyHead; while (cur.next != null) { if (cur.next.val == val) { // 删除节点并连接 cur.next = cur.next.next; } else { cur= cur.next; } } return dummyHead.next; }
4.删除链表元素（237-易）
题目描述：函数参数传入要删除的节点，即在O(1)时间复杂度删除该节点。，所以不能遍历链表查找元素。
示例：
输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
思路：由于题目没有给出头结点，我们无法遍历链表（遍历也不满足时间复杂度要求），更不知道要删除节点的前一个节点，这样我们就不能使用传统的方式删除。
虽然不知道前驱节点，但我们知道要删除节点的下一个节点，解决方案：将要删除的节点赋值为下一个节点的值，然后转化为删除下一个节点。例如：
[4,5,1,9], node = 5 -> [4,1,1,9], 这时就可以删除当前节点的下一个节点。
代码实现：
public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; }
5. 删除链表的倒数第 n 个节点(19-中/剑指22)
题目描述：删除链表的倒数第 n 个节点，返回链表的头结点。进阶：使用一次遍历！
剑指22要求输出链表中的倒数第n个节点，而不是删除，其实想一下，我们想一下我们在19中删除是先找到这个待删除的点，但是现在我们找的不是倒数第n个节点，而是他的前继节点，然后做返回（类似删除），代码大同小异，自行实现。
示例：
1.删除链表倒数第n个节点 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 2.输出链表中的倒数第n个节点 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
思路：
法1：两次遍历比较简单，第一次遍历计算链表长度，第二次遍历找到该点删除（找到删除节点的上一个节点）。注意：需要单独判断删除头节点的问题!
法2：在递归求解链表长度时删除，递归的组织方式是从后向前，即当递归遍历到第n个节点就表示链表倒数第n个节点，我们需要在递归时找到倒数第n+1个节点，改变指针就可以。
法3：进阶问题：可以使用快慢指针，将倒数第n个元素对称位置作为快指针起点！！当快指针到达终点，慢指针的坐标即为待删除节点！原理：快慢指针的行程相同。
ps：假设链表长度len，那么快指针位于第n个节点位置，再走len - n到达终点，这时慢指针也走了len - n，这样我们就省去了求链表长度的过程，一次遍历即可删除。
代码：
// 代码1：两次遍历 public ListNode removeNthFromEnd(ListNode head, int n) { ListNode cur = head; int len = 0; while (cur != null) { len++; cur = cur.next; } cur = head; int k = len - n; if (k == 0) return head.next; // 删除头结点 while (k-- > 1) { cur = cur.next; //获取待删除的前一个节点 } cur.next = cur.next.next; return head; } //代码2：递归求解 public ListNode removeNthFromEnd_1(ListNode head, int n) { int pos = length(head, n); if (pos == n) return head.next; //单节点时，即删除头结点 return head; } private int length(ListNode node, int n) { if (node == null) return 0; int pos = length(node.next, n) + 1; // 遍历到倒数第n+1个节点，即待删除节点的前一个节点 if (pos == n + 1) { node.next = node.next.next; } return pos; } // 代码3：快慢指针(推荐，很巧妙！！) public ListNode removeNthFromEnd_3(ListNode head, int n) { ListNode fast = head, slow = head; // 快指针起点（对称位置） while (n-- > 0) { fast = fast.next; } if (fast == null) return head.next; //删除倒数第n节点！（链表长度n） while (fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return head; }
6.移除重复节点（面试题02.01）
题目描述：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点（说明相对位置不能变），保证最后返回的结果中元素唯一。
进阶：如果不得使用临时缓冲区，该怎么解决？
示例：
输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
思路：注意不能改变节点的相对顺序，所以先排序后删除的方案不可取！
- 法1：可以使用set进行去重，遍历链表，遇到相同的元素过滤（类似删除链表中的指定节点，但这里不是全部删除，不需要虚拟节点），但使用了额外空间 。
- 法2：双重循环：双指针，一个指向一个固定的值比如m，另一个从m的下一个节点开始扫描，如果遇到和m相同的节点，直接删除，时间复杂度O(n^2)，效率比较低。
// 代码1：哈希表 public ListNode removeDuplicateNodes(ListNode head) { if (head == null) { return head; } Set<Integer> set = new HashSet<>(); ListNode cur = head; while (cur != null && cur.next != null) { set.add(cur.val); if (set.contains(cur.next.val)) { // 已经存在该元素，直接删除 cur.next = cur.next.next; } else { cur = cur.next; } } return head; } // 代码2：双重循环 public ListNode removeDuplicateNodes(ListNode head) { if (head == null) { return head; } ListNode p = head; while (p != null) { ListNode q = p; while (q.next != null) { if (p.val == q.next.val) { // 删除重复元素 q.next = q.next.next; } else { q = q.next; } } p = p.next; } return head; }
