题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

样例

算法思路： 双指针算法，归并排序

c++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto i = l1, j = l2;
        auto dummy = new ListNode(-1);
        auto p = dummy;
        while(i && j)
        {
            if(i->val <= j->val){
                p -> next = i;
                p = i;
                i = i->next;
            }
            else{
                p -> next = j;
                p = j;
                j = j->next;
            }
        }
        while(i){
            p -> next = i;
            p = i;
            i = i->next;
        }

        while(j){
            p -> next = j;
            p = j;
            j = j->next;
        }

        return dummy->next;
    }
};