[leetcode] 143. Reorder List 파이썬 코드

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

 

연결리스트를 이런 순서로 reorder 해야 한다.

 

 

연결리스트를 반으로 나눴을 때 첫 번째 파트는 그대로 방향을 유지하면 된다.

그런데 두 번째 파트는 맨 마지막에 포인터를 두고 끝에서 앞쪽으로, 즉 reverse 시킬 수 있다.

그렇게 alternating 시키면서 두 연결리스트를 merge 시키면 된다.

 

그런데 중간 지점을 어떻게 찾을 것인가?

slow pointer와 fast pointer를 사용하면 된다.

 

그 다음에 새로운 연결 리스트를 만들지 않고, 원래 연결 리스트를 사용해서 만들 수 있다.

그러면 공간 복잡도는 O(1)이 된다.

이 때 가장 첫 번째 노드에서 1st 포인터가 시작되고, 가장 끝 노드에서 2nd 포인터가 시작된다.

그런데 reorder 해줘야 하니까 1st 포인터나 2nd 포인터 링크가 break 되는데 

1st 포인터의 next 값이 필요하므로 break 하기 전에 미리 temp 로 그 연결을 저장해야 한다.

 

그리고 마지막 노드는 Null을 가리키게 한다.

 

class Solution(object):
    def reorderList(self, head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next # shift by 1
            fast = fast.next.next # shift by 2
        second = slow.next
        slow.next = None # split the linkedlist into half
        
        # reverse the second half of the list
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        
        # merge two halfs
        first, second = head, prev
        while second:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2

 

 

 

 

참고

https://www.youtube.com/watch?v=S5bfdUTrKLM&t=226s