Leetcode Python - 86. Partition List

Leetcode #86 - Partition List

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 86 ‘Partition List’을 파이썬으로 풀어 보도록 하겠습니다.

머리가 안돌아서.. discuss를 보도록 하겠습니다. 포인트는 두개의 ListNode를 선언해 하나는 x보다 작은 값을 연결한 linked list를 만들고, 다른 하나는 x보다 같거나 큰 값을 연결한 linked list를 만드는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def partition(self, head, x):
        l1 = h1 = ListNode(0)
        l2 = h2 = ListNode(0)
        
        while head:
            if head.val < x:
                l1.next = head
                l1 = l1.next
            else:
                l2.next = head
                l2 = l2.next
            head = head.next
        
        l1.next = h2.next
        l2.next = None
        return h1.next

시간복잡도는 O(n) : linked list를 한 번 loop

공간복잡도는 O(n) : linked list를 나누어 2개의 새로운 linked list로 선언