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

LeetCode Partition List

編輯:C++入門知識

LeetCode Partition List


LeetCode解題之Partition List


原題

給定一個鏈表以及一個目標值,把小於該目標值的所有節點都移至鏈表的前端,大於等於目標值的節點移至鏈表的尾端,同時要保持這兩部分在原先鏈表中的相對位置。

注意點:

鏈表的排序一般通過重新連接指針來完成

例子:

輸入: head = 1->4->3->2->5->2, x = 3

輸出: 1->2->2->4->3->5

解題思路

看成有一串珠子,有紅和藍兩種顏色,現在要把紅色和藍色分別集中到一起。可以遍歷每個珠子,如果是藍色就串在一條線上,紅色的串在另一條線上,最後把兩條線連起來就可以了。注意,在比較大的那串數中,最後的指針要置為None,因為那是排序後的最後一個節點。

AC源碼

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def to_list(self):
        return [self.val] + self.next.to_list() if self.next else [self.val]


class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)

        prev = dummy
        small_prev = small_dummy
        large_prev = large_dummy
        while prev.next:
            curr = prev.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            prev = prev.next
        large_prev.next = None
        small_prev.next = large_dummy.next
        return small_dummy.next


if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(4)
    n3 = ListNode(3)
    n4 = ListNode(2)
    n5 = ListNode(5)
    n6 = ListNode(2)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    n5.next = n6
    r = Solution().partition(n1, 3)
    assert r.to_list() == [1, 2, 2, 4, 3, 5]

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