[leetcode题解]21.Merge two Sorted Lists(两排序链表合并)

leetcode,21,Merge Two Sorted Lists,单链表合并问题,合并两个已排序链表为一个完整的已排序链表。
直接使用两个指针依次比较其中值大小即可,小的插入,并且指针后移,最后不要忘记把剩下的非空链表加入链尾。
此题的升级版本为leetcode,23,Merge K Sorted Lists

c++代码:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode *pre = new ListNode(-1);
        ListNode *tail = pre;
        
        while(l1 != NULL && l2 != NULL)
        {
            if (l1->val < l2->val)
            {
                tail->next = l1;
                tail = tail->next;
                l1 = l1->next;
            }
            else
            {
                tail->next = l2;
                tail = tail->next;
                l2 = l2->next;
            }
        }
        
        if (l1 != NULL)
        {
            tail->next = l1;
        }
        else 
        {
            tail->next = l2;
        }
        return pre->next;
    }
};

python代码:

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        pre = ListNode(-1)
        tail = pre
        
        while l1 is not None and l2 is not None:
            t = None
            if l1.val < l2.val:
                t = l1
                l1 = l1.next
            else:
                t = l2
                l2 = l2.next
            tail.next = t
            tail = tail.next
        if l1 is not None:
            tail.next = l1
        else:
            tail.next = l2
        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]21.Merge two Sorted Lists(两排序链表合并)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/107.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注