剑指offer–合并两个排序的链表

一、前言

最近开始刷剑指offer，记录一下。牛客网在线编程板块的剑指offer专区。 牛客网剑指offer：传送门 或者点击下方链接。 https://www.nowcoder.com/ta/coding-interviews

二、题目描述

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

三、代码

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here # 需要四个指针 # 1、判断边界条件 if pHead1 == None: return pHead2 if pHead2 == None: return pHead1 # 2、判断头指针 newHead = pHead1 if pHead1.val < pHead2.val else pHead2 pTmp1 = pHead1 pTmp2 = pHead2 if newHead == pTmp1: pTmp1=pTmp1.next else: pTmp2=pTmp2.next previousPoint=newHead while pTmp1 and pTmp2: if pTmp1.val < pTmp2.val: previousPoint.next = pTmp1 previousPoint=pTmp1 pTmp1=pTmp1.next else: previousPoint.next = pTmp2 previousPoint=pTmp2 pTmp2=pTmp2.next if pTmp1 == None: previousPoint.next = pTmp2 else: previousPoint.next= pTmp1 return newHead