Merge Two Sorted Lists

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

http://www.lintcode.com/en/problem/merge-two-sorted-lists/

Solution

非常简单，用个dummy node来确定head，省得讨论各种case。

class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode dummy = ListNode(-1);
        ListNode *cur = &dummy;
        while (l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1:l2;
        return dummy.next;
    }
};

再来个优雅的递归写法。再说一遍，递归两件事：一、什么时候终止递归；二、怎么处理当前case和下一个case之间的 关系。

class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        if(l1 == NULL) {
            return l2;//终止条件
        }
        if(l2 == NULL) {
            return l1;
        }
        ListNode *mergedHead = NULL;
        if(l1->val < l2->val) {//当前case和下个case之间的关系
            mergedHead = l1;
            mergedHead->next = mergeTwoLists(l1->next, l2);
        } else {
            mergedHead = l2;
            mergedHead->next = mergeTwoLists(l1, l2->next);
        }
        return mergedHead;
    }
};