【剑指 offer】合并链表

描述：

输入两个递增的链表，单个链表的长度为 n，合并这两个链表并使新链表中的节点仍然是递增排序的。

思路：

定义一个新链表，先进行我们的原俩链表判断，然后比较俩链表的每个节点大小，然后往后走，新链表按照递增的排序进行插入，最后注意，俩链表长度可能不一样，走完一个直接拼接另外一个剩下的节点

public class Solution {public ListNode mergeTwoLists(ListNode head1, ListNode head2) {if (head1 == null) return head2;if (head2 == null) return head1;ListNode newHead = new ListNode(-1);ListNode tmp = newHead;while(head1 != null && head2 != null){if(head1.val < head2.val){tmp.next = head1;tmp = tmp.next;head1 = head1.next;}else {tmp.next = head2;tmp = tmp.next;head2 = head2.next;}}if(head1 != null){tmp.next = head1;}if(head2 != null){tmp.next = head2;}return newHead.next;}
}