반응형
문제 링크
문제 설명
단일 연결 리스트의 헤드가 주어지면 홀수 인덱스를 가진 모든 노드와 짝수 인덱스를 가진 노드를 함께 그룹화하고 재정렬된 리스트를 반환합니다.
첫 번째 노드는 홀수로 간주되고 두 번째 노드는 짝수로 간주됩니다. 짝수 그룹과 홀수 그룹 내부의 상대적인 순서는 입력에서 그대로 유지되어야 합니다.
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
반응형
댓글