题目链接:合并两个有序链表
分析:
有两个链表 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;
}
}