【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