Merge k Sorted Lists

标签： C++ 算法 LeetCode 链表

每日算法——leetcode系列

问题 Merge Two Sorted Lists

Difficulty: Easy

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.

/**
 * 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) {
        
    }
};

翻译

合并两个有序链表

难度系数：简单

合并两个有序链表并返回一个新链表。新的链表的由两个有序的链表的节点组成。

思路

两种思考方式：

• 先定一个主链表，把另一个链表合并到这个主链表
  假定一个链表dummy, 为方便遍历，设dummy的初始值为-1，next指向l1(主链表)，为返回值，还得新那家一个链表tempLink = dummy

• 如果l1的值比l2小，templink = l1, 再遍历l1->next

• 如果l1的值比l2大，则把temlink->next = l2, tempLink = tempLink->next, 再把tempLink批回主链表， 这样到最后有可能副链表还不为空，再加到后面就好

• 直接同时遍历两个链表，再每次取其中小的
  这种思路比较直接，就是同时遍历两个链表， 哪个小用哪个， 再把剩下的放到最后

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *p1 = l1,  *p2=l2;
        ListNode dummy(-1);
        dummy.next = p1;
        ListNode *tempLink = &dummy;
        
        while(p1 != nullptr && p2 != nullptr) {
            if (p1->val < p2->val) {
                tempLink = p1;
                p1 = p1->next;
            } else {
                tempLink->next = p2;
                p2 = p2->next;
                tempLink = tempLink->next;
                tempLink->next = p1;
            }
        }
        if (p2 != nullptr) {
            tempLink->next = p2;
        }
        
        return dummy.next;
    }
    
    ListNode* mergeTwoLists2(ListNode* l1, ListNode* l2) {
        ListNode *p1 = l1,  *p2=l2;
        ListNode dummy(-1);
        dummy.next = nullptr;
        ListNode *tempLink = &dummy;
        
         while(p1 != nullptr && p2 != nullptr) {
            if (p1->val < p2->val) {
                tempLink->next = p1;
                p1 = p1->next;
                tempLink = tempLink->next;
            } else {
                tempLink->next = p2;
                p2 = p2->next;
                tempLink = tempLink->next;
            }
        }
        if (p2 != nullptr) {
            tempLink->next = p2;
        } else if ( p1 != nullptr) {
            tempLink->next = p1;
        }
        
        return dummy.next;
    }

};