LeetCode 链表专题 3：设立链表的虚拟头结点

作者: 李威威 | 来源:发表于2019-05-28 23:16 被阅读0次

LeetCode 链表专题 3：设立链表的虚拟头结点
数据结构-链表和递归
2019-01-12 Day 7
【剑指Offer 16】反转链表
链表—虚拟头结点
Day73 排序链表
LRU 缓存
合并两个排序链表
2019-01-21 Day16
第十六周

这是处理链表问题常用的技巧。

例1：LeetCode 第 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、==掌握递归写法==。重点：千万不要忘记，还有递归写法。

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

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;
    }
}

练习

练习1：LeetCode 第 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：LeetCode 第 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;
    }
    
}

（本节完）