算法@LeetCode:MergeTwoSortedLists

Log

• 【170419】完成 01 版（Python）提交与笔记
• 【170423】研究过参考答案并记录

题目

Merge Two Sorted Lists

【题目类型备注】

链表

提交

01

【语言】

Python

【时间】

170419

【思路】

很基础的链表题，基本思路就是两个指针分别指向两个链表中的结点，比较大小，然后用正确的顺序断开、重建结点间的连接。想清楚下述情况并处理好即可：

1. 结点值严格不等时
2. 结点值相等时
3. 结点数不等时
4. 如果两个链表中的结点数值排序是交叉的（例如 [1, 3, 5'] 与 [2, 4, 6]），怎么处理；如果某个链表中出现连续的几个结点比另一个链表中的结点来得小，怎么处理
5. 到了结尾如何处理
6. 算法何时结束

【代码】

# 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)
        if l1 and l2:
          # if both not none
          if l1.val <= l2.val:
            head = l1
          else:
            head = l2
        elif l1: 
          # l2 is None
          return l1
        else:
          # l1 is None
          return l2

        finished = False
        recent = 1 
        now = 1-recent
        count = 0
        while not finished:
          if l1.val == l2.val:
            l = [l1, l2]
            p = l[now].next
            l[now].next = l[recent]
            l[now] = p
            if now == 0:
              l1, l2 = l[now], l[recent]
            else:
              l2, l1 = l[now], l[recent]
            recent = now
            now = 1-recent
            if p is None:
              finished = True
          else:
            # l"1" < l"2"
            if l1.val < l2.val:
              now = 0
              l = [0, l1, l2]
            else:
              now = 1
              l = [0, l2, l1]
            while (l[1].next) and (l[1].next.val <= l[2].val):
              l[1] = l[1].next
            if l[1].next:
              p = l[1].next
              l[1].next = l[2]
              l[1] = p
              if 0 == now:
                l1, l2 = l[1], l[2]
              else:
                l2, l1 = l[1], l[2]
            else:
              l[1].next = l[2]
              if 0 == now:
                l1, l2 = l[1], l[2]
              else: 
                l2, l1 = l[1], l[2]
              finished = True

        return head

【结果】

运行时：56 ms

报告链接：https://leetcode.com/submissions/detail/100557943/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 65.08% of python submissions.

虽然是很基础的题目，但是由于不熟悉 Python 语言，踩了巨大的坑：

把对象放到列表中后使用时要小心。例如名为 obj 的对象 <obj> 放到 l=[] 中后，l = [obj]；对 l[0] 进行修改后，l[0] 就不再是 <obj> 了，而是 <obj_new>，除非你在修改后执行了 obj = l[0]，否则使用 obj 时指向的仍然是 <obj> 而非 <obj_new>。

本来用列表包装对象是为了少写代码，结果踩了这么一个大坑……不过不管怎么说也算值了。还好只是在练习中踩的坑。

00

参考解法：

• Python：2 种非递归写法 + 1 种递归写法
• C++
  • 1：递归写法
  • 2：非递归写法
• Java

所有上述参考代码都比我来得简洁明了。思路无需多言，代码特别清晰（其中 Python 的 3 种解法里，最后一种非递归需要画图一下才会比较清楚；我会更倾向于看前两种，也就是递归写法，以及第一种非递归写法）。我也不知道当时为什么踩到了那样的坑……把问题想复杂了。

自己实现一遍最优解：

• [date-language] 。。。