题目

将两个排序链表合并为一个新的排序链表。http://www.lintcode.com/zh-cn/problem/merge-two-sorted-lists/

分析

很基础的题目，把一个链表中的元素逐一取出，插入到另一个链表即可，注意一下头结点的特殊处理就完了。

代码

public class Solution {
    
    ListNode mergeList(ListNode head, ListNode node){
        if(head == null) return node;
        if(node.val < head.val){
            node.next = head;
            return node;
        }
        
        ListNode pre = head;
        for(ListNode current = head.next; current != null && (current.val < node.val); current = current.next){
            pre = current;
        }
        node.next = pre.next;
        pre.next = node;
        return head;
    }
    /*
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // write your code here
        for(; l2 != null ;){
            ListNode temp = l2;
            l2 = l2.next;
            temp.next = null;
            l1 = mergeList(l1, temp);
        }
        return l1;
    }
}