数据结构将两个有序的链表合并为一个新链表

问题描述

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。
比如{1，4} {3，5}，合并就是{1，3，4，5}；

解题思路

首先我们要判定是否有一个链表为空，都为空，返回空，一个为空，则返回不为空的那个；其次找到，两个链表的第一个节点，比较小的那个，作为主链（head），将另一个的节点元素，依次比较，并入其中，最后肯定有一个链表先走完，那么只需要把未走完后续链表并入就好了。

代码展示

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
if(l1 == null) return l2;
if(l2 == null) return l1;
//先处理头
ListNode head = (l1.val <= l2.val)? l1:l2;
ListNode tail = head;
l1 = (head == l1)? l1.next:l1;
l2 = (head == l2)? l2.next:l2;
while(l1 != null && l2 != null)
{
if(l1.val <= l2.val){
tail.next = l1;
l1 = l1.next;
}else{
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 == null)? l2 : l1;
return head;
}