合并两个有序链表

我会带着你远行 2021-10-30 08:20 493阅读 0赞

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

  1. 示例：
  3. 输入：1->2->4, 1->3->4
  4. 输出：1->1->2->3->4->4

代码1：递归法

  1. def mergeTwoLists(self,l1,l2):
  2.     if l1 is None:        #如果为空
  3.         return l2         #返回链表l2
  4.     elif l2 is None:      #如果l2为空
  5.         return l1         #返回l1
  6.     elif l1.val < l2.val: #如果链表1上的值比链表2上的值小
  7.         l1.next = self.mergeTwoLists(l1.next,l2) #那么把当前小的
  8.                                       #结点的后继指向作为剩下结点的头结点
  9.         return l1 
  10.     else:
  11.         l2.next = self.mergeTwoLists(l1,l2.next) #同上
  12.         return l2

通常做法：

  1. def mergeTwoLists(self,l1,l2):
  2.     #maintain an unchanging reference to node ahead of the return node.
  3.     prehead = ListNode(-1)
  4.     prev = prehead #prev为游动指针
  5.     while l1 and l2:
  6.         if l1.val <= l2.val:
  7.             prev.next = l1 #游动指针为后继结点为l1
  8.             l1 = l1.next #l1指针移到下一个位置
  9.         else:
  10.             prev.next = l2
  11.             l2 = l2.next
  12.         prev = prev.next #游动指针往后移动一个位置
  13.     #exactly one of l1 and l2 can be non-null at this point, so connect
  14.     #the non-null list to the end of merged list.
  15.     prev.next = l1 if l1 is not None else l2
  17.     return prehead.next

发表评论

表情：
评论列表 （有 0 条评论，493人围观）

还没有评论，来说两句吧...

相关阅读

    相关 合并两个有序链表

    合并两个有序链表 1、题目 题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输

    灰太狼灰太狼/ 0 赞/ 152 阅读