1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

	public ListNode Merge(ListNode pHead1, ListNode pHead2) {
    // 任一链表为空，直接返回另一个链表
    if (pHead1 == null || pHead2 == null) {
        return pHead1 == null ? pHead2 : pHead1;
    }

    // 选择两个链表头中值更小的作为合并后的头节点
    ListNode mergeHead = pHead1.val < pHead2.val ? pHead1 : pHead2;

    // currSelected：选中头节点的链表的下一个节点
    ListNode currSelected = mergeHead.next;
    // currOther：未选中头节点的另一个链表的头节点
    ListNode currOther = mergeHead == pHead1 ? pHead2 : pHead1;
    // pre：合并链表的尾节点
    ListNode pre = mergeHead;

    while (currSelected != null && currOther != null) {
        // 选择值更小的节点拼接到合并链表尾部
        if (currSelected.val <= currOther.val) {
            pre.next = currSelected;
            currSelected = currSelected.next; // 选中链表指针后移
        } else {
            pre.next = currOther;
            currOther = currOther.next; // 另一个链表指针后移
        }
        pre = pre.next; // 合并链表尾节点后移
    }

    // 拼接剩余未遍历完的链表
    pre.next = currSelected == null ? currOther : currSelected;

    return mergeHead;
}