【leetcode刷题】20T15-合并两个有序链表

• 2020 年 2 月 16 日
• 笔记

木又同学2020年第15篇解题报告

leetcode第21题：合并两个有序链表

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

【题目】

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：  输入：1->2->4, 1->3->4  输出：1->1->2->3->4->4  

【思路】

从头结点开始，比较两个链表l1和l2的元素，哪个链表的元素小，则新链表的尾部节点指向该元素，同时元素较小的原链表指针后移。

需要注意的是，在元素比较结束后，一定记得把剩余的元素添加到新链表中（肯定有一个链表未访问到所有元素）。

【代码】

python版本

# Definition for singly-linked list.  # class ListNode(object):  #     def __init__(self, x):  #         self.val = x  #         self.next = None    class Solution(object):      def mergeTwoLists(self, l1, l2):          """          :type l1: ListNode          :type l2: ListNode          :rtype: ListNode          """          head = ListNode(0)          p = head          head1, head2 = l1, l2            # 比较两个链表节点的大小，插入新链表中          while head1 and head2:              if head1.val < head2.val:                  p.next = head1                  head1 = head1.next              else:                  p.next = head2                  head2 = head2.next              p = p.next            # 可能链表并未访问结束          while head1:              p.next = head1              head1 = head1.next              p = p.next          while head2:              p.next = head2              head2 = head2.next              p = p.next          return head.next