leetcode medium : partition list

Partition List - LeetCode

Partition List - LeetCode

 

O(N) space complexity를 생각하고 two scan하면 진짜 쉽게 풀 수 있다

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        answer = ListNode()
        tail = answer
        
        p = head
        while p:
            if p.val < x:
                tail.next = ListNode(p.val)
                tail = tail.next
            
            p = p.next
            
        p = head
        while p:
            if p.val >= x:
                tail.next = ListNode(p.val)
                tail = tail.next
                
            p = p.next
        
        return answer.next

 

낫 배드~

 

다른 사람 풀이도 궁금하네

ListNode *partition(ListNode *head, int x) {
    ListNode node1(0), node2(0);
    ListNode *p1 = &node1, *p2 = &node2;
    while (head) {
        if (head->val < x)
            p1 = p1->next = head;
        else
            p2 = p2->next = head;
        head = head->next;
    }
    p2->next = NULL;
    p1->next = node2.next;
    return node1.next;
}

 

one pass C++ solution 지린다..ㅋㅋㅋㅋㅋㅋ

 

파이썬 버전

def partition(self, head, x):
    hd1=p1=ListNode(0)
    hd2=p2=ListNode(0)

    while head:
        if head.val<x:
            p1.next=head
            p1=p1.next
        else:
            p2.next=head
            p2=p2.next
        head=head.next

    p2.next=None
    p1.next=hd2.next
    return hd1.next

 

새 노드를 생성하면서 정답 리스트를 만드는게 아니라

기존 리스트를 가리키게만 하는거라서 공간절약의 극한을 맛볼수있다.

돌려볼까?

 

뭐 설명이 필요있을까..

역시 leetcode discussion ㅋㅋㅋㅋ