【LeetCode】21. Merge Two Sorted Lists 合并两个有序链表

作者：负雪明烛
id： fuxuemingzhu
个人博客：http://fuxuemingzhu.cn/
个人公众号：负雪明烛
本文关键词：合并，有序链表，递归，迭代，题解，leetcode, 力扣，Python, C++, Java

题目描述

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

题目大意

把两个有序列表合并成一个有序列表。

解题方法

迭代

直接自己定义一个链表的头，循环两个链表，每次把两个链表头部较小的那个节点放到结尾。最后不要忘了如果链表有剩余，应该拼接起来。

Python解法

这个题有个升级版本23. Merge k Sorted Lists，比这题有意思，可以看看。

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def mergeTwoLists(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

        """

        head = ListNode(0)

        move = head

        if not l1: return l2

        if not l2: return l1

        while l1 and l2:

            if l1.val < l2.val:

                move.next = l1

                l1 = l1.next

            else:

                move.next = l2

                l2 = l2.next

            move = move.next

        move.next = l1 if l1 else l2

        return head.next

C++解法

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

        if (!l1) return l2;

        if (!l2) return l1;

        ListNode* dummy = new ListNode(0);

        ListNode* cur = dummy;

        while (l1 && l2) {

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

                cur->next = l1;

                l1 = l1->next;

            } else {

                cur->next = l2;

                l2 = l2->next;

            }

            cur = cur->next;

        }

        if (l1) cur->next = l1;

        else  cur->next = l2;

        return dummy->next;

    }

};

Java解法

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { liebiaoval = x; }

 * }

 */

public class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head=new ListNode(0);

        ListNode move=head;

        while(l1!=null && l2!=null){

            if(l1.val<=l2.val){

                move.next=l1;

                l1=l1.next;

            }else{

                move.next=l2;

                l2=l2.next;

            }

            move=move.next;

        }

        if(l1!=null){

            move.next=l1;

        }else{

            move.next=l2;

        }

        return head.next;

    }

}

AC:1ms

递归

递归很好写了，这个函数是把两个有序的merge，所以找到当前的小的节点，然后把后面的继续merge就好了。

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def mergeTwoLists(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

        """

        if not l1 and not l2:

            return None

        elif not l1:

            return l2

        elif not l2:

            return l1

        if l1.val <= l2.val:

            node = l1

            node.next = self.mergeTwoLists(l1.next, l2)

        else:

            node = l2

            node.next= self.mergeTwoLists(l1, l2.next)

        return node

日期

2016/5/1 19:35:14
2018 年 3 月 11 日
2018 年 11 月 18 日 —— 出去玩了一天，腿都要废了
2019 年 1 月 11 日 —— 小光棍节？

秒客网