20190804 阿里面试编程题总结

• 阿里数据库岗，二面技术面，最后一题编程题

  # 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
  

• 用list很容易，但是重新把列表作为一个类出现得时候脑子开始空白。

  # 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):
  

• 没有仔细看这个类是怎么定义得，只看到了示例数据得格式，结果陷入得怎么也没办法把测试数据声明成这样类得困境，在短时间内没有解决问题。记录一下。

• 后来发现是Leetcode 的第21题，看完解法之后才发现自己思路是对的，但是错误就在没看类的定义导致自己全盘都乱了。

伪代码，错误示范

11.next = 11.val
if 11.next != None:
    if 11.val > 12.val:
    11.next = 12.val

解法

• 因为Node 记录的是val和next，这两个列表其实直接比较大小，得出哪个是head，哪个是tail就可以解决问题，自己把问题复杂化。

  if l1 == None:
      return l2
  if l2 == None:
      return l1
  
  if l1.val <= l2.val:
      head = l1 
      head.next = self.mergeTwoLists(l1.next, l2)
  else:
      head = l2
      head.next = self.mergeTwoLists(l1, l2.next)
  
  return head 
  

内置库的解法

# Solution 1
# using sorted()
# to combine two sorted lists
res = sorted(test_list1 + test_list2)

## Solution 2 heapq.merge
from heapq import merge
# to combine two sorted lists
res = list(merge(test_list1, test_list2))

# printing result
print("The combined sorted list is : " + str(res))

在我忘记sort是升序还是降序的情况下，复杂解法

def two(list_a, list_b):
list_c = []
while len(list_a) > 0 and len(list_b) > 0:
    if list_a[0] < list_b[0]:
        list_c.append(list_a[0])
        del list_a[0]
    else:
        list_c.append(list_b[0])
        del list_b[0]
list_c.extend(list_a)
list_c.extend(list_b)
return list_c

ret = two([1, 2, 4], [1, 3, 4])
print(ret)

总结

• 代码不够熟练度不够。读题不够仔细，没看清楚类的声明是最大的问题。
• 心态不能崩，崩了之后智商为0。不够冷静。