虚拟头节点和双指针解决链表问题（合并，与分解操作，力扣题目为例）

Problem: 21. 合并两个有序链表
Problem: 86. 分隔链表

总览说明

在解决链表相关的算法题目时较多使用到的技巧就是虚拟头节点、双指针，而题目往往都会涉及到对链表的分解、合并操作，本文选择两个题目将其利用技巧进行相关合并、分解操作显现出来；其中21题目主要体现合并操作，也较好理解；主要要注意86题目中在分解时的一个细节（下文会展示出来）

题目描述

21. 合并两个有序链表

86. 分隔链表
    

思路

21题

1.创建虚拟头节点dummy和尾指针p指向dummy；创建指针p1和p2分别指向list1和list2；
2.当p1和p2均不为空时，若p1.val > p2.val:

2.1.使得p指向p2；
2.2.p2指针后移；
2.3.tail指针后移，并使得tail -> next至空

3.若p1 -> val < = p2 -> val时，对p1执行与2类似的操作；
4.若p1和p2其中之一不为空，则将tail -> next指向它；并最后放回dummy -> next

86题

1.创建两个虚拟头节点dummy1（用于依次顺序存储原链表中比x值小的节点）、dummy2（用于依次顺序存储原链表中比x值大的节点）；指针p1指向dummy1、p2指向dummy2，指针p指向初始链表表头head
2.将相关节点的合并操作同21题目类似（留给读者独立思考），此处主要要注意分解时的一个细节：每次先使用一个指针temp记录p.next,再将p.next置空，最后再让p指向temp（可能读者读到此处也感觉比较唐突，不妨可以先试着看如下代码先自己思考一下为什么）
3.最后将两个链表连接并返回正确的表头（由于前面是保证了依次顺序存储，所以题目要求的保持相对位置不变的要求也得到了实现）

复杂度

两道题目均如下
时间复杂度:

$O(n)$;

空间复杂度:

$O(n)$

Code

21题

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // virtual head node
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode p = dummy;

        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            // compare pointers p1 and p2
            // attach the node with smaller value to the pointer
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // advance the p pointer
            p = p.next;
        }

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

86题

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // virtual head node for the list soring nodes less than x
        ListNode dummy1 = new ListNode(Integer.MIN_VALUE);
        // virtual head node for the list soring nodes greater than x
        ListNode dummy2 = new ListNode(Integer.MIN_VALUE);

        // p1, p2 pointers are responsible for creating the result list
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        // p is responsible for traversing the original

        ListNode p = head;
        while (p != null) {
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next; 
            } else {
                p1.next = p;
                p1 = p1.next;
            }
            // Not move p pointer directly,
            // disconnect the next pointer of each node in the original list
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        // connect the two lists
        p1.next = dummy2.next;
        
        return dummy1.next;
    }
}

总结分析

在21题目中主要是利用双指针进行一步步比较，再利用虚拟头节点去将其连接到一起
在86题目中其实最终要的是断开原来链表之间的连接（p.next = null;）所以由于需要断开原来链表之间的连接，所以无法直接移动p，需要先用一个指针记录当前指针p的下一个节点位置，再进一步来实现移动p的操作（那么为什么需要这样操作而不是就直接像21题目那样直接移动p指针呢？读者仔细自己举出一个例子模拟那种代码走一遍就会发现如果那样的话最后是存在环的），其实最主要的一点就是如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的（注意是可能必要），有时不断开也没什么影响但是断开却能保证不会出现不必要的错误