查看题目详情可点击此处。
题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路
首先两个链表都是有序的，那就是需要解决一条链的某几个连续结点需要插入另一条链的两个结点之间的情况，我将两条链分为主链和支链，结点遍历只在主链上发生，支链只负责将头结点与主链被遍历到的当前结点比对，当比当前结点小时就将支链插入当前结点之前，支链融合为主链，此时的当前结点及其之后的结点都被转化为支链，继续之前的操作，直到支链为NULL为止，代码如下。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {return l2;}
if(l2 == null) {return l1;}
ListNode head = l1;
ListNode bh = l2;
if(l2.val < l1.val) {
head = l2;
bh = l1;
}
ListNode curr = head.next;
ListNode prev = head;
while(bh != null) {
if(lessThanNode(curr, bh)) {
prev.next = bh;
bh = curr;
curr = prev.next;
}
prev = curr;
curr = curr.next;
}
return head;
}
private boolean lessThanNode(ListNode node, ListNode lessNode) {
if(node == null) {return true;}
if(lessNode == null) {return false;}
return lessNode.val < node.val;
}
}
