程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Merge Two Sorted Lists

LeetCode Merge Two Sorted Lists

編輯:C++入門知識

LeetCode Merge Two Sorted Lists


LeetCode解題之Merge Two Sorted Lists


原題

將兩個有序的鏈表拼接成一個有序的鏈表。

注意點:

不需要額外申請節點,主要把原鏈表中的節點串聯起來 原鏈表中的一個已經全部在新鏈表中後,另一個鏈表剩余的部分可以直接拼接

例子:

輸入: l1 = 1->2->4, l2 = 3
輸出: 1->2->3->4

解題思路

為了避免分類討論,添加一個假的頭節點。現在只需要兩個指針分別指向原來的兩個鏈表,將其中比較小的節點添加到新的鏈表中。傳入的參數l1和l2正好可以當作遍歷兩個鏈表的指針。

AC源碼

# 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
        """
        temp = ListNode(-1)
        head = temp
        while l1 and l2:
            if l1.val > l2.val:
                temp.next = l2
                l2 = l2.next
            else:
                temp.next = l1
                l1 = l1.next
            temp = temp.next
        if l1:
            temp.next = l1
        else:
            temp.next = l2
        return head.next


if __name__ == "__main__":
    assert Solution().mergeTwoLists(ListNode(1), ListNode(2)).val == 1

歡迎查看我的Github來獲得相關源碼。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved