【题目】

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

【分析】

无

【代码】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 21.Merge Two Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-two-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(-1);
        ListNode *p1 = l1,*p2 = l2,*cur = head;
        while(p1 != NULL && p2 != NULL){
            // 取两个链表头的较小元素
            if(p1->val < p2->val){
                cur->next = p1;
                p1 = p1->next;
            }//if
            else{
                cur->next = p2;
                p2 = p2->next;
            }//else
            cur = cur->next;
        }//while
        // 如果链表1没有遍历完
        while(p1){
            cur->next = p1;
            p1 = p1->next;
            cur = cur->next;
        }//while
        // 如果链表2没有遍历完
        while(p2){
            cur->next = p2;
            p2 = p2->next;
            cur = cur->next;
        }//while
        cur->next = NULL;
        return head->next;
    }
};

int main() {
    Solution solution;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    // 链表1
    ListNode *head1 = new ListNode(A[0]);
    ListNode *p1 = head1;
    for(int i = 1;i < 5;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    // 链表2
    ListNode *head2 = new ListNode(B[0]);
    ListNode *p2 = head2;
    for(int i = 1;i < 6;i++){
        ListNode *node = new ListNode(B[i]);
        p2->next = node;
        p2 = node;
    }//for
    ListNode *head = solution.mergeTwoLists(head1,head2);
    // 输出
    ListNode *p = head;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}

【代码二】

递归实现

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        if(l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

【代码三】

public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(-1);
        for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
            int val1 = (l1 == NULL) ? INT_MAX : l1->val;
            int val2 = (l2 == NULL) ? INT_MAX : l2->val;
            if(val1 <= val2){
                p->next = l1;
                l1 = l1->next;
            }//if
            else{
                p->next = l2;
                l2 = l2->next;
            }//else
        }//for
        return head->next;
    }
};