LeetCode 21. Merge Two Sorted Lists合并两个有序链表 (C++)

题目：

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.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

分析：

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

创建一个新的节点head，比较了l1和l2的值的大小，将较小的加入到head，依次比较，如果l1，l2有剩余，就接在后面即可。

l1　　　　　　　　 l2 head，p

↓　　　　　　　　 ↓　　　　　　　　 ↓

1->2->4　　　　　　1->3->4 0

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓ ↓

2->4　　　　　　　1->3->4 0->1

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓　　 ↓

2->4　　　　　　 3->4 0->1->1

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓　　　 ↓

4　　　　　　 3->4 0->1->1->2

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓　　　　 ↓

4　　　　　　 4 0->1->1->2->3

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓　　　　 ↓

null　　　　　　 4 0->1->1->2->3->4

l1　　　　　　　　 l2 head p

↓　　　　　　　　 ↓　　　　　　　　 ↓　　　　 ↓

null　　　　　　 null 0->1->1->2->3->4->4

最后返回head.next即可。

还可以递归求解此问题。

mergeTwoLists( l1, l2) //l1:1->2->4，l2:1->3->4

=>{1} + mergeTwoLists( l1, l2) //l1:2->4，l2:1->3->4

=>{1->1} + mergeTwoLists( l1, l2) //l1:2->4，l2:3->4

=>{1->1->2} + mergeTwoLists( l1, l2) //l1:4，l2:3->4

=>{1->1->2->3} + mergeTwoLists( l1, l2) //l1:4，l2:4

=>{1->1->2->3->4} + mergeTwoLists( l1, l2) //l1，l2:4

=>{1->1->2->3->4->4}

程序：

/**

 * 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) {

        ListNode head();

        ListNode* p = &head;

        while(l1 && l2){

            if(l1->val < l2->val){

                p->next = l1;

                l1 = l1->next;

            }

            else{

                p->next = l2;

                l2 = l2->next;

            }

            p = p->next;

        }

        if(l1) p->next = l1;

        if(l2) p->next = l2;

        return head.next;

    }

};

//递归

class Solution {

public:

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        if(l1 == nullptr) return l2;

        if(l2 == nullptr) return l1;

        if(l1->val < l2->val){

            l1->next = mergeTwoLists(l1->next, l2);

            return l1;

        }

        else{

            l2->next = mergeTwoLists(l1, l2->next);

            return l2;

        }

    }

};

巴特西

LeetCode 21. Merge Two Sorted Lists合并两个有序链表 (C++)

题目：

分析：

程序：

最新文章

热门文章