Leetcode 合并两个有序链表
Leetcode 合并两个有序链表
Categories:
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路
初始化一个新的链表want节点, 并用head变量保存头部
当l1和l2都不为空时, 比较两个链表的头部元素, 较小的赋值给新链接want, 并将链接指针后移
当l1或l2有一个为空时, 将不为空的链接剩余节点追加到want
最后返回head->next(即真正的链接第一个元素)
Answer
1#
2# @lc app=leetcode.cn id=21 lang=python3
3#
4# [21] 合并两个有序链表
5#
6
7# @lc code=start
8# Definition for singly-linked list.
9# class ListNode:
10# def __init__(self, val=0, next=None):
11# self.val = val
12# self.next = next
13class Solution:
14 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
15 want = ListNode(0)
16 head = want
17 while l1 and l2:
18 if l1.val <= l2.val:
19 tmp = ListNode(l1.val)
20 l1 = l1.next
21 else:
22 tmp = ListNode(l2.val)
23 l2 = l2.next
24 want.next = tmp
25 want = want.next
26 if l1:
27 want.next = l1
28 if l2:
29 want.next = l2
30 return head.next
31# @lc code=end
Accepted
208/208 cases passed (44 ms)
Your runtime beats 78.91 % of python3 submissions
Your memory usage beats 7.14 % of python3 submissions (13.8 MB)