Merge Two Sorted Lists - 每日算法

每日算法——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;    }};