「链表」专题 3：设立虚拟头结点
这是处理链表问题常用的技巧。
例1：「力扣」第 203 题：移除链表元素
传送门：英文网址：203. Remove Linked List Elements ，中文网址：203. 删除链表中的结点 。
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
思路：先给出一个容易想到的解法，但是这个解法对于删除头结点的逻辑写得比较长。
Java 代码：（代码比较冗长，没有意义，可以跳过不看，只要跟头结点有关的问题，要设置虚拟头结点就好了。）
/**
* 基本思路：只要当前遍历的节点的下一个节点不为空
* 把它拿出来比较一下目标值：
* 如果和目标值相同，就（1）先把要删除的节点存一下。
* （2）当前的节点的下一个引用指向要删除节点的下一个引用。
* （3）把要删除节点的下一个节点的引用置为 null。
* 但是，特别要注意：这种方法对于，如果要删除的节点是头结点的方式，并不适用
*
* @param head
* @param value
* @return
*/
public ListNode removeElements(ListNode head, int value) {
// 这里陷阱很多，要特别注意测试用例为"要删除的节点值连续出现在链表表头的情况"
// 例如，待考察链表 {1, 1, 1, 2, 3, 4, 5} ，待删除的元素的值是 1 的情况
// 为了删除头结点，我们编写了很长的一段代码
while (head != null && head.val == value) {
ListNode delNode = head;
head = delNode.next;
delNode = null;
}
if (head == null) {
return null;
}
ListNode current = head;
while (current.next != null) {
if (current.next.val == value) {
ListNode delNode = current.next;
current.next = delNode.next;
delNode.next = null;
} else {
current = current.next;
}
}
return head;
}下面介绍一种设立链表的虚拟头结点的技巧，使得删除头结点的逻辑可以合并到删除非链表头结点的逻辑中。
思路很简单，就是在待考察的链表前面加上一个虚拟结点，使得原来的头结点不是头结点。
Java 代码：
public ListNode removeElements(ListNode head, int value) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode current = dummyHead;
while (current.next != null) {
if (current.next.val == value) {
ListNode delNode = current.next;
current.next = delNode.next;
delNode = null;
} else {
current = current.next;
}
}
ListNode retNode = dummyHead.next;
dummyHead = null;
return retNode;
}思路：
1、使用虚拟头结点；
2、掌握递归写法。
重点：千万不要忘记，还有递归写法。
Java 代码：
public ListNode removeElements(ListNode head, int val) {
// 首先处理递归到底的情况，直接返回 null
if (head == null) {
return head;
}
// 假设下一个结点开始的链表已经处理完了
ListNode res = removeElements(head.next, val);
// 再将头结点和除了头结点以外的链表部分合并考虑
if (head.val == val) {
return res;
} else {
head.next = res;
return head;
}
}Python 代码：使用递归，假设小一个规模的问题已经求解，然后处理原问题。
class Solution:
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if head is None:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head练习
练习1：「力扣」第 82 题：删除排序链表中的元素 II
传送门：82. 删除排序链表中的重复元素 II。
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5 输出: 1->2->5示例 2:
输入: 1->1->1->2->3 输出: 2->3
关键：要两个两个一起判断。
Python 代码：
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
dummy = ListNode(-1)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
# 继续往后看，有没有相等的元素
# del_node 至少删掉它
del_node = cur.next.next
while del_node.next and del_node.val == del_node.next.val:
del_node = del_node.next
# 开始删除操作
cur.next = del_node.next
del_node.next = None
else:
cur = cur.next
return dummy.next练习2：「力扣」第 21 题：合并两个有序链表
传送门：英文网址：21. Merge Two Sorted Lists ，中文网址：21. 合并两个有序链表 。
分析：归并两个有序的链表，还是穿针引线的问题，用递归也可以做。
Java 代码：使用递归最简单。
public class Solution3 {
/**
* 使用递归
*
* @param l1 有序链表
* @param l2 有序链表
* @return 有序链表
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}Java 代码：使用穿针引线。
/**
* https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
*/
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
/**
* @author liwei
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode p1 = l1;
ListNode p2 = l2;
ListNode curNode = dummyNode;
// 两者都不为空的时候，才有必要进行比较
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
// 指针修改发生在这里
curNode.next = p1;
p1 = p1.next;
} else {
// 指针修改发生在这里
curNode.next = p2;
p2 = p2.next;
}
curNode = curNode.next;
}
// 跳出循环是因为 p1 == null 或者 p2 == null
if (p1 == null) {
curNode.next = p2;
}
if (p2 == null) {
curNode.next = p1;
}
return dummyNode.next;
}
}
（本节完）
