题目描述

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

解题思路

先创建一个新的链表表头，然后比较两个排序的链表，将较小的值接在新链表的后面，最后将排序链表有
剩余的部分直接接入链表即可。

  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     # 返回合并后列表
  8.     def Merge(self, pHead1, pHead2):
  9.         #创建一个新的链表
  10.         newhead=ListNode(-1)
  11.         cur=newhead
  12.         #遍历并比较两个排序的链表的值，将值较小结点的接入新链表
  13.         while pHead1 and pHead2:
  14.             if pHead1.val<pHead2.val:
  15.                 cur.next=pHead1
  16.                 pHead1=pHead1.next
  17.                 cur=cur.next
  18.             else:
  19.                 cur.next=pHead2
  20.                 pHead2=pHead2.next
  21.                 cur=cur.next
  22.         #若pHead1有剩余部分
  23.         if pHead1:
  24.             cur.next=pHead1
  25.         #若pHead2有剩余部分
  26.         if pHead2:
  27.             cur.next=pHead2
  28.         return newhead.next