Python_100DaysofCode/Partition_List_Day56.py at main · ayushlingayat/Python_100DaysofCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#Brute Approach
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        values = []
        while head:
            values.append(head.val)
            head = head.next

        new_vals = [v for v in values if v < x] + [v for v in values if v >= x]

        dummy = ListNode(0)
        curr = dummy
        for v in new_vals:
            curr.next = ListNode(v)
            curr = curr.next

        return dummy.next

# Time: O(n) (one traversal to collect + one to rebuild)
# Space: O(n) (array + new list)

#Better Approach
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        smaller_dummy = ListNode(0)
        greater_dummy = ListNode(0)

        small = smaller_dummy
        great = greater_dummy

        while head:
            if head.val < x:
                small.next = ListNode(head.val)
                small = small.next
            else:
                great.next = ListNode(head.val)
                great = great.next
            head = head.next

        small.next = greater_dummy.next
        return smaller_dummy.next

# Time: O(n)
# Space: O(n) (since creating new nodes)

#Optimal Approach

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        smaller_dummy = ListNode(0)
        greater_dummy = ListNode(0)

        small = smaller_dummy
        great = greater_dummy

        while head:
            if head.val < x:
                small.next = head
                small = small.next
            else:
                great.next = head
                great = great.next
            head = head.next

        great.next = None  # Important: avoid cycle
        small.next = greater_dummy.next
        return smaller_dummy.next

# TC - O(n)
# SC - O(1)