Fork me on GitHub

Partition List

Posted on

Description

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

Solution

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        smaller = ListNode(-1)
        bigger = ListNode(-1)
        tra_smaller = smaller
        tra_bigger = bigger
        traverse = head
        
        while traverse != None:
            if traverse.val < x:
                tra_smaller.next = traverse
                traverse = traverse.next
                tra_smaller = tra_smaller.next
            else:
                tra_bigger.next = traverse
                traverse = traverse.next
                tra_bigger = tra_bigger.next
        tra_bigger.next = None
        tra_smaller.next = bigger.next
        return smaller.next