首页 > 编程语言 > 详细

链表 21. 归并两个有序的链表 python

时间:2021-07-11 17:42:26      阅读:21      评论:0      收藏:0      [点我收藏+]

21. Merge Two Sorted Lists (Easy)

  • 链表问题可以考虑哑节点(相当于就是头结点,或者一个哨兵)。

    • 思路一:迭代
      需要三个指针,一个哑节点。哑节点的val值默认为-1.
      1. 比较l1和l2的大小,哑节点指向小的那个
      2. l1和l2中小的那个后移
      3. 在接着比较现在l1和l2中val的大小,重复1,2步骤直致结束。
  • 思路二:递归

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        cur = dummy_head = ListNode(-1)
        while l1 and l2:
            if l1.val > l2.val:
                cur.next = l2
                l2 = l2.next
                cur = cur.next
            else:
                cur.next = l1
                l1 = l1.next
                cur = cur.next
        
        if l1:
            cur.next = l1
        elif l2:
            cur.next = l2
        else: 
            cur.next = None
        return dummy_head.next

链表 21. 归并两个有序的链表 python

原文:https://www.cnblogs.com/zzychage/p/14998802.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!