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

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
// 核心思想：设置傀儡节点，dum，cur代替dum去遍历
// 判断 l1.val 和 l2.val 的大小 注意 l1.val 可能等于 l2.val
// 注意：题上给出的示例都是 l1 和 l2 长度一样，但是我们必须考虑到
// l1 和 l2 长度不同的时候
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        
        // 首先设置傀儡节点 
        ListNode dum = new ListNode(-1);
        // 设置 cur 指针 代替 傀儡节点去遍历
        ListNode cur = dum;
        // 开始链接，进入循环，此时注意循环条件
        // 其中一个链表（l1或者l2）走完，跳出循环
        while(list1 !=null && list2 != null) {
            // 先比较 l1.val 和 l2.val
            // 谁小，那么cur指针指向谁
            if(list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next; // list1 往后走
            }else {
                cur.next = list2;
                list2 = list2.next;// list2 往后走
            }
            cur = cur.next; // cur 往后走
        }  
        // 跳出循环之后，有一条链已经走完，我们需要判断，并且将剩下的
        // 拼接
        cur.next = list1 != null ? list1 : list2;
        // 最后返回头节点
        return dum.next;
    }
}