LeetCode初級演算法–鏈表02：合併兩個有序鏈表

• 2019 年 10 月 21 日
• 筆記

LeetCode初級演算法–鏈表02：合併兩個有序鏈表

搜索微信公眾號:’AI-ming3526’或者’電腦視覺這件小事’ 獲取更多演算法、機器學習乾貨
csdn：https://blog.csdn.net/baidu_31657889/
csdn：https://blog.csdn.net/abcgkj/
github：https://github.com/aimi-cn/AILearners

一、引子

這是由LeetCode官方推出的的經典面試題目清單~
這個模組對應的是探索的初級演算法~旨在幫助入門演算法。我們第一遍刷的是leetcode推薦的題目。
查看完整的劍指Offer演算法題解析請點擊github鏈接：
github地址

二、題目

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例:

輸入：1->2->4, 1->3->4  輸出：1->1->2->3->4->4

1、思路

首先我們看到的數一個有序的鏈表，所以我們可以先比較兩個鏈表長度相等的部分，按照順序進行排列，對於剩下一個鏈表的部分，直接插入到最終的鏈表中，詳細過程見程式碼。

2、編程實現

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          """          new_head = ListNode(0)          #返回的是合併後的列表 所以讓一個節點等於這個空的節點          pHead = new_head          #進行排序          while l1 and l2:              if l1.val > l2.val:                  new_head.next = l2                  l2 = l2.next              else:                  new_head.next = l1                  l1 = l1.next              new_head = new_head.next          # 遍歷剩下沒遍歷的列表          if l1:              new_head.next = l1          elif l2:              new_head.next = l2          return pHead.next

AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料

分享技術，樂享生活：我們的公眾號電腦視覺這件小事每周推送「AI」系列資訊類文章，歡迎您的關注！

本文由部落格一文多發平台 OpenWrite 發布！