[오답노트] LeetCode #328 Odd Even Linked List

교훈
편법 부릴 생각 말고 정석으로 조금만 더 고민해봐라. 답이 생각보다 쉬울 수도 있다.

빨리 가는 유일한 방법은 제대로 가는 것이다.

로버트 C. 마틴 (Rovert C. Martin)

• LeetCode 문제 링크
• 출처 : 박상길 저, 파이썬 알고리즘 인터뷰, p.233

문제

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

홀수번째 노드가 다 온 뒤에, 짝수번째 노드가 뒤에 모여 있는 식으로 linked list를 수정하라.

The first node is considered odd, and the second node is even, and so on.

첫번째 노드는 홀수, 두번째 노드는 짝수... 이런 식으로 분류한다.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

홀수 그룹과 짝수 그룹 내에 모여 있는 순서는 기존 순서를 유지해야 한다.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

O(1)의 추가적인 공간을 사용하고, O(n)의 시간 복잡도를 가져야 한다.

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Constraints:

• n == number of nodes in the linked list
• 0 <= n <= 104
• -106 <= Node.val <= 106

발상

Solution #1

리스트로 바꾼 뒤에 슬라이싱으로 만들고 이으면 되잖아?

class Solution:
    def toList(self, node: Optional[ListNode]) -> List: # 위의 책, p.222
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    def toLinkedList(self, list: List) -> Optional[ListNode]:
        root = ListNode()
        head = root
        for i in range(len(list)):
            head.next = ListNode(list[i])
            head = head.next
        return root.next

    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:       
        return self.toLinkedList(self.toList(head)[::2] + self.toList(head)[1::2])

통과는 한다.

Success
Runtime: 79 ms, faster than 13.06% of Python3 online submissions for Odd Even Linked List.
Memory Usage: 17.2 MB, less than 5.33% of Python3 online submissions for Odd Even Linked List.

그런데 이렇게 푸는 게 정석일리가 없지 않은가?
출제자는 LinkedList의 next를 자유자재로 다룰줄 아는지 궁금했을 것이다.

Solution #2

이 의도를 충실히 이행하고자 골똘히 고민해보면, 방법을 찾는 게 어려운 일은 아니다.

1. 두 노드씩 반복하면서, next를 바로 다음 노드가 아니라 다음 다음 노드를 가리키게 함으로써 홀수 번째 노드와 짝수 번째 노드를 구분한다.
2. 두 노드 모두 끝에 다다르면, 홀수 번째 노드의 끝은 짝수 번째 노드의 시작으로 연결하고, 짝수번째 노드의 끝에는 None을 할당한다.

풀이

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        odd = head
        even = head.next
        tmp = head.next # 짝수번째 시작을 기억

        while even and even.next: # 첫번째는 이미 위에서 검사했다. 두번째 세번째를 차례로 검사해야, NullPointer를 참조하는 불상사가 안 생긴다. 
            odd.next = odd.next.next
            odd = odd.next

            even.next = even.next.next
            even = even.next

        odd.next = tmp
        return head