python实现合并两个排序的链表

剑指offer：合并两个排序的链表，python实现

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

吐槽

本来想用递归实现，但是大脑卡壳，没有想到合适的递归策略，潜意识里还是把两个链表当成两个数组来看待，写出了非递归版本的代码。写完后回看自己写的代码，逻辑不够一目了然，中间变量过多，代码过长，一定不是好代码。上网查阅，发现一个如此美妙的递归版本，哇，写的好美啊！！！看来我对递归的了解和灵活应用还不够啊，至少在链表上还不够啊！！！

解题思路

思路1（非递归，low）

找到两个链表中头节点值相对更小的链表，将其作为主链表，第二个链表中的元素则不断加入到主链表中。具体策略是：主链表定义两个指针，指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时，将第二个链表的当前元素插入到主链表两个指针指向的元素中间，并调整指针指向。

python代码

def merge(self, phead1, phead2):
 if not phead1:
  return phead2
 if not phead2:
  return phead1
 mainhead = phead1 if phead1.val <= phead2.val else phead2
 sechead = phead2 if mainhead == phead1 else phead1
 mergehead = mainhead
 mainnext = mainhead.next
 while mainnext and sechead:
  if sechead.val <= mainnext.val:
   mainhead.next = sechead
   sechead = sechead.next
   mainhead.next.next = mainnext
   mainhead = mainhead.next
  else:
   mainhead = mainnext
   mainnext = mainnext.next
 if not mainnext:
  mainhead.next = sechead
 return mergehead

思路2（递归版本，better）

网上找到的java版本，思路如此清晰，以至于用任何额外的文字描述都显得多余。我用python重现了思路，代码如下。哎，美妙的代码如此的赏心悦目，流连忘返啊…

def merge(self, phead1, phead2):
 if not phead1:
  return phead2
 if not phead2:
  return phead1
 if phead1.val <= phead2.val:
  phead1.next = self.merge(phead1.next, phead2)
  return phead1
 else:
  phead2.next = self.merge(phead1, phead2.next)
  return phead2

最后给出包含测试部分的全部代码：

class solution:

 def merge(self, phead1, phead2):
  if not phead1:
   return phead2
  if not phead2:
   return phead1
  if phead1.val <= phead2.val:
   phead1.next = self.merge(phead1.next, phead2)
   return phead1
  else:
   phead2.next = self.merge(phead1, phead2.next)
   return phead2

 def getnewchart(self, list):
  if list:
   node = listnode(list.pop(0))
   node.next = self.getnewchart(list)
   return node

class listnode:
 def __init__(self, x):
  self.val = x
  self.next = none

if __name__ == '__main__':
 list1 = [1, 3, 5]
 list2 = [0, 1, 4]
 testlist1 = solution().getnewchart(list1)
 testlist2 = solution().getnewchart(list2)
 final = solution().merge(testlist1, testlist2)
 while final:
  print(final.val, end=" ")
  final = final.next

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。