[Leetcode/Python] 328. Odd Even Linked List

문제 링크

Odd Even Linked List - LeetCode

 

문제 설명

단일 연결 리스트의 헤드가 주어지면 홀수 인덱스를 가진 모든 노드와 짝수 인덱스를 가진 노드를 함께 그룹화하고 재정렬된 리스트를 반환합니다.

첫 번째 노드는 홀수로 간주되고 두 번째 노드는 짝수로 간주됩니다. 짝수 그룹과 홀수 그룹 내부의 상대적인 순서는 입력에서 그대로 유지되어야 합니다.

O(1) 공간 복잡도 및 O(n) 시간 복잡도에서 문제를 해결해야 합니다.

 

 여기서 착각하지 말아야 할점이 node.val을 기준으로 나누는 것이 아니다. 노드가 n번째에 있을때 n이 짝수인 것과 홀수인 것을 나눠야 한다.

 

입출력 예시

Head	output
[1,2,3,4,5]	[1,3,5,2,4]
[2,1,3,5,6,4,7]	[2,3,6,7,1,5,4]

 

제한 사항

• 노드의 갯수는 [0, 10^4] 사이에 존재한다.
• -10^6 <= Node.val <= 10^6

 

문제 풀이

처음의 node.val을 기준으로 홀수와 짝수를 나누는줄 알았다. 하지만 문제를 다시 읽어보면 노드의 순서에 따라 홀수와 짝수를 나누는 것이다.

 

 이 문제에서 중요한 것은 공간복잡도는 O(1)이며, 시간복잡도는 O(n)이다. 즉 노드는 한번만 탐색이 가능하고, 따로 복사본을 만들면 안된다. 해결하기 위해서는 얕은복사를 이용하면 된다.

 

소스코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        target = head.next
        odd_tail = head
        even_tail = ListNode()
        odd_tail.next = even_tail
        count = 2
        while target:
            temp = target
            target = target.next
            if count % 2 == 0 :
                even_tail.next = temp
                temp.next = None
                even_tail = temp
            else:
                temp.next = odd_tail.next
                odd_tail.next = temp
                odd_tail = temp
            count += 1
        odd_tail.next = odd_tail.next.next
        return head

 

 

코딩 테스트, 어떻게 대비해야 할까?