LinkedList : Reorder List

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

LeetCode - The World's Leading Online Programming Learning Platform

 

왼쪽끝, 오른쪽끝, 왼쪽끝에서 두번째, 오른쪽 끝에서 두번째.. 이런식으로 양끝에서 점점 가운데로 오는 순으로 노드를 재배치하는 문제다.

언뜻생각하면 이걸 어떻게 O(1) space로 풀지 라고 생각할 수 있는데 가능하다.

slow&fast pointer기법으로 중앙을 찾은뒤 중앙 기준 오른쪽 노드들을 전부 reverse시킨다. 그리고 왼쪽끝과 오른쪽끝 포인터를 가지고 한칸씩 전진시키며 리스트를 reorder하면 된다.

 

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return head

        dummy = ListNode(0, head)

        # reverse list
        mid = self.findMiddle(head)
        prev, cur = mid, mid.next
        while cur:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        rightend = prev

        # reorder list
        left, right, pointer, is_left = dummy.next, rightend, dummy, True
        while left != right:
            if is_left:
                pointer.next = left
                pointer = left
                left = left.next
            else:
                pointer.next = right
                pointer = right
                right = right.next

            is_left = not is_left
        
        # make last node points None
        left.next = None


    def findMiddle(self, head):
        if not head or not head.next:
            return head

        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow