虚拟头结点

虚拟头结点是在处理链表操作时的技巧,主要功能在于能使操作的链表不在需要关心新建头结点的初始状态或空指针的情况,在逻辑代码中能将所有结点一视同仁。

看一道题就很清楚了:

虚拟头结点

 

 

很简单的题,解法为:

 

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;

    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }

    if (p1 != null) {
        p.next = p1;
    }

    if (p2 != null) {
        p.next = p2;
    }

    return dummy.next;
}

代码中用到一个链表的算法题中是很常见的「虚拟头结点」技巧,也就是 dummy 节点

可以试试,如果不使用 dummy 虚拟节点,代码会复杂很多,而有了 dummy 节点这个占位符,可以避免处理空指针的情况,在最后只需要返回 dummy,next 降低代码的复杂性

 

虚拟头结点

上一篇:Sword 内存屏障-缓存一致性协议


下一篇:扩展赋值运算符和条件运算符