[LeetCode]题解（python）：021-Merge Two Sorted Lists-白红宇

[LeetCode]题解（python）：021-Merge Two Sorted Lists

阅读量：5923 次

发布时间：2019-06-19

本文共 1736 字，大约阅读时间需要 5 分钟。

题目来源：

　　https://leetcode.com/problems/merge-two-sorted-lists/

题意分析：

　　题目给出两个排好序的链表，将这两个链表整合成一个新的有序的链表。

题目思路：

　　这道题目很简单，首先构造一个新的链表，比较两个链表的指针指向的节点的值大小，将值较少的节点放到新链表中，并将指针位置往后移动一位，直到某个链表为空之后，把剩下的链表全部放到新的链表中就可以了。时间复杂度是（O（m+n））

代码（python）：

1 # Definition for singly-linked list. 2 # class ListNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.next = None 6  7 class Solution(object): 8     def mergeTwoLists(self, l1, l2): 9         """10         :type l1: ListNode11         :type l2: ListNode12         :rtype: ListNode13         """14         ans = ListNode(0)15         tmp = ans16         if l1 == None and l2 == None:17             return None18         while l1 !=None or l2 != None:19             if l1 == None:20                 while l2 != None:21                     tmp.val = l2.val22                     l2 = l2.next23                     if l2 == None:24                         break25                     tmp.next = ListNode(0)26                     tmp = tmp.next27                 break28             if l2 == None:29                 while l1 != None:30                     tmp.val = l1.val31                     l1 = l1.next32                     if l1 == None:33                         break34                     tmp.next = ListNode(0)35                     tmp = tmp.next36                 break37             if l1.val <= l2.val:38                 tmp.val = l1.val39                 l1 = l1.next40             else:41                 tmp.val = l2.val42                 l2 = l2.next43             tmp.next = ListNode(0)44             tmp = tmp.next45         return ans

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4872779.html

转载于:https://www.cnblogs.com/chruny/p/4872779.html

你可能感兴趣的文章