题目链接:合并两个有序链表

分析:

有两个链表  L1 和 L2

首先要判断的是,给定的两个链表是否存在 null 的情况

L1为空 ,那么返回的是L2;L2为空,返回的是L1

当两个链表 都不为空,就需要进行判断,有序输出

因为是有序链表,所以就省了很多事

先用L1的node1和L2的node1对比,哪个小,我们就输出谁(正序输出)

假设L1的node1小,把node1输出后,还需要继续再次进行比较

L1的node2和L2的node1进行比较,哪个小就输出谁

等到最后,若有一个链表变为null

那就直接把另一支链表剩下的元素全部输出就可以了

 

代码实现:

public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        // 判断两个队列是否为空的情况
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        // 当两个队列不为空,新建立一个头结点
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            // 判断哪个节点的 value更小一些
            boolean chk = (l1.val < l2.val);
            // 哪个链表的 val值更小一些,cur.next就指向谁
            cur.next = chk ? l1 : l2;
            // cur指针向前移动一位
            cur = cur.next;
            // l1更小,继续输出 l1; 否则 l1的值不变
            l1 = chk ? l1.next : l1;
            // l2更小,继续输出 l2; 否则 l2的值不变
            l2 = chk ? l2 : l2.next;
        }
        // 当其中一个队列变为空的时候
        cur.next = (l1 == null) ? l2 : l1;
        return head.next;
    }
}