本文共 2633 字，大约阅读时间需要 8 分钟。
题目描述：
合并两个已排序的链表，并将其作为一个新列表返回。新列表应该通过拼接前两个列表的节点来完成。
解题思路：
构造一个新的链表空间，利用链表的next依次组合，不难，就是生疏了忘了链表看了下。
代码：
# Definition for singly-linked list.#class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ newnode = ListNode(None) # define the res ListNode if l1 ==None and l2 == None: # l1 and l2 both are none return None if l1 == None: # l1 is none return l2 if l2 == None: # l2 is none return l1 # initialize the res ListNode if l1.val >= l2.val: newnode = l2 l2 = l2.next else: newnode = l1 l1 = l1.next res = newnode while l1 != None and l2 != None: # l1 and l2 record in the res if l1.val <= l2.val: res.next = l1 res = res.next l1 = l1.next else: res.next = l2 res = res.next l2 = l2.next if l1 != None: # l1 is not none but l2 is none res.next = l1 res = res.next l1 = l1.next if l2 != None: # l2 is not none but l1 is none res.next = l2 res = res.next l2 = l2.next return newnode
# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here res = head = ListNode(0) while pHead1 and pHead2: if pHead1.val > pHead2.val: head.next = pHead2 pHead2 = pHead2.next else: head.next = pHead1 pHead1 = pHead1.next head = head.next if pHead1: head.next = pHead1 if pHead2: head.next = pHead2 return res.next
# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 pHead = None if pHead1.val <= pHead2.val: pHead = pHead1 pHead.next = self.Merge(pHead1.next, pHead2) else: pHead = pHead2 pHead.next = self.Merge(pHead1, pHead2.next) return pHead
转载地址：http://qhyii.baihongyu.com/