BM4题解 | #合并两个排序的链表#

Java 双指针

遇到这种不确定头节点的情况下，需要设置一个虚拟头结点dummyHead，返回的时候返回dummyHead.next节点即可。

三个指针，pHead1, pHead2, p 分别对应链表1、链表2、合并链表

while循环用两条链表都非空作为循环条件

循环中每次让p指向小值的节点，小值链表指针向后移一位，合并链表的指针p也要后移一位

最后如果两条链表长度不相同，最后循环结束一定是一条空，一条非空，那么还需要把p（也就是合并链表末尾节点）的next指向非空节点

最后返回dummyHead.next就是合并后的链表

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        // write code here
        ListNode dummyHead = new ListNode(-1);
        ListNode p = dummyHead;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val > pHead2.val) {
                p.next = pHead2;
                pHead2 = pHead2.next;
            } else { // pHead1.val <= pHead2.val
                p.next = pHead1;
                pHead1 = pHead1.next;
            }
            p = p.next;
        }
        if (pHead1 == null) {
            p.next = pHead2;
        }
        if (pHead2 == null) {
            p.next = pHead1;
        }
        return dummyHead.next;
    }
}