단일 연결 리스트(singly linked list)가 주어졌을 때, 홀수 번째 위치에 있는 노드들을 모두 앞쪽으로 모으고 그 뒤에 짝수 번째 위치의 노드들을 이어 붙여야 합니다. 여기서 중요한 점은 노드에 저장된 값이 아니라 노드의 위치(인덱스)를 기준으로 한다는 것입니다. 또한 추가 메모리 없이 기존 노드의 포인터만 조작하는 제자리(in-place) 방식으로 해결하는 것이 좋습니다.
예를 들어 노드가 [1, 22, 13, 14, 25]로 구성되어 있다면, 1번째·3번째·5번째(홀수) 노드인 1, 13, 25가 먼저 오고, 그 뒤에 2번째·4번째(짝수) 노드인 22, 14가 이어져 최종 결과는 [1, 13, 25, 22, 14]가 됩니다.
알고리즘 접근 방법
두 개의 포인터를 사용해 홀수 노드 체인과 짝수 노드 체인을 동시에 만들고, 마지막에 두 체인을 하나로 연결하는 방식입니다. 단계별 과정은 다음과 같습니다.
- 종료 조건 확인: head가 null이거나 head의 다음 노드가 null이면(노드가 0개 또는 1개뿐이면) 재배열이 필요 없으므로 head를 그대로 반환합니다.
- 포인터 초기화: head1 := head(홀수 체인의 끝), head2 := head의 다음 노드(짝수 체인의 끝), head_beg := head의 다음 노드(짝수 체인의 시작점)로 설정합니다.
- 반복 분리: head2의 다음 노드와 다다음 노드가 모두 null이 아닌 동안 아래 작업을 반복합니다.
- head1.next := head2.next → 홀수 체인 뒤에 다음 홀수 노드를 연결
- head2.next := head2.next.next → 짝수 체인 뒤에 다음 짝수 노드를 연결
- head1 := head1.next, head2 := head2.next → 각 포인터를 한 칸씩 전진
- 마지막 노드 처리: 반복 종료 후 head2.next가 null이 아니라면(전체 노드 개수가 홀수인 경우), 남은 마지막 홀수 노드를 홀수 체인에 연결하고 head1을 전진시킵니다.
- 체인 연결: head1.next := head_beg로 홀수 체인 뒤에 짝수 체인을 연결하고, head2.next := null로 짝수 체인의 끝을 정리합니다.
- 결과 반환: head를 반환합니다.
구현 예제
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end="")
while ptr:
print(ptr.val, end=", ")
ptr = ptr.next
print(']')
class Solution(object):
def oddEvenList(self, head):
if head == None or head.next == None:
return head
head1 = head
head2, head2_beg = head.next, head.next
while head2.next != None and head2.next.next != None:
head1.next = head2.next
head2.next = head2.next.next
head1 = head1.next
head2 = head2.next
if head2.next != None:
head1.next = head2.next
head1 = head1.next
head1.next = head2_beg
head2.next = None
return head
ob1 = Solution()
head = make_list([1, 22, 13, 14, 25])
print_list(ob1.oddEvenList(head))
입력
[1,22,13,14,25]
출력
[1, 13, 25, 22, 14]
복잡도 및 정리
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 포인터 몇 개만 추가로 사용하므로 공간 복잡도는 O(1)입니다. 홀수 위치 노드와 짝수 위치 노드를 각각 별도의 체인으로 이어 붙인 뒤 마지막에 합치는 방식이기 때문에, 새로운 노드를 생성하거나 값을 복사하지 않고도 기존 노드들의 next 포인터만 변경하여 문제를 효율적으로 해결할 수 있습니다.