0086._partition_list.md

86. Partition List

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/partition-list/description/

内容描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

两个dummy,一个代表before，一个代表behind，最后连接起来就是结果，要注意behind的最后可能还连接着原来的点

例如例子中的5，它在最开始后面还连接着1个2，所以要记得将dummy1_end.next置为None

beats 99.39%

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """       
        dummy1_start = dummy1_end = ListNode(None) # before
        dummy2_start = dummy2_end = ListNode(None) # behind
        while head:
            if head.val < x:
                dummy1_end.next = head
                dummy1_end = dummy1_end.next
            else:
                dummy2_end.next = head
                dummy2_end = dummy2_end.next
            head = head.next
        # 从例子来看,因为dummy2_end最后指向5,它最开始还连着2呢,所以要置为空
        dummy2_end.next = None 
        dummy1_end.next = dummy2_start.next
        return dummy1_start.next