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

整体思路：

1. 创建一个虚拟头节点 dummy，它的值可以是任意的，这个节点的作用是为了简化代码逻辑。
2. 使用一个指针 current 来迭代合并后的链表，初始时指向虚拟头节点。
3. 使用循环，直到其中一个链表为空。在循环中，比较两个链表当前节点的值，将较小的节点接到 current 的后面，并将对应链表的指针向后移动一位。
4. 循环结束后，可能存在一个链表已经遍历完，但另一个链表还有剩余节点未处理，所以需要进一步处理。
5. 返回虚拟头节点的下一个节点，即合并后链表的头节点。

这个算法的时间复杂度为 O(m+n)，其中 m 和 n 分别是两个链表的长度，因为需要遍历两个链表来进行合并。

import java.util.Scanner;

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取第一个链表
        ListNode pHead1 = readList(scanner);
        
        // 读取第二个链表
        ListNode pHead2 = readList(scanner);
        
        // 合并两个链表
        ListNode mergedList = merge(pHead1, pHead2);
        
        // 输出合并后的链表
        printList(mergedList);
    }
    
    // 读取链表
    public static ListNode readList(Scanner scanner) {
        String[] elements = scanner.nextLine().split("\\s+");
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        for (String element : elements) {
            int val = Integer.parseInt(element);
            current.next = new ListNode(val);
            current = current.next;
        }
        
        return dummy.next;
    }
    
    // 合并两个有序链表
    public static ListNode merge(ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                current.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                current.next = pHead2;
                pHead2 = pHead2.next;
            }
            current = current.next;
        }
        
        if (pHead1 != null) {
            current.next = pHead1;
        }
        if (pHead2 != null) {
            current.next = pHead2;
        }
        
        return dummy.next;
    }
    
    // 输出链表
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}