문제 개요
단일 연결 리스트(singly linked list)가 하나 있다고 가정해 보겠습니다. 이 리스트를 마지막 노드 → 첫 번째 노드 → 뒤에서 두 번째 노드 → 앞에서 두 번째 노드 순서로 재배열해야 합니다. 즉, 뒤쪽 노드와 앞쪽 노드를 번갈아 가며 배치하는 것이 목표입니다.
예를 들어 입력이 [1,2,3,4,5,6,7,8,9]라면 출력은 [9, 1, 8, 2, 7, 3, 6, 4, 5]가 됩니다.
해결 전략
핵심 아이디어는 간단합니다. 먼저 모든 노드의 값을 임시 리스트에 순서대로 저장한 뒤, 리스트의 끝에서 하나 꺼내고(pop()), 앞에서 하나 꺼내고(pop(0)) 이 작업을 반복하며 원래 노드에 차례대로 덮어쓰는 것입니다. 파이썬 리스트의 pop()은 스택처럼 뒤에서, pop(0)은 큐처럼 앞에서 요소를 제거하므로 이 문제에 딱 맞는 도구입니다.
단계별로 정리하면 다음과 같습니다.
- c := 헤드(head) 노드, l := 빈 리스트로 초기화
- c가 null이 아닌 동안 반복:
- c의 값을 l의 끝에 추가
- c := c.next
- c를 다시 헤드 노드로 설정
- c가 null이 아니고 l이 비어 있지 않은 동안 반복:
- c.val := l.pop() — 마지막 요소를 꺼내 저장하고 제거
- c := c.next
- c가 null이면 루프 탈출
- c.val := l.pop(0) — 첫 번째 요소를 꺼내 저장하고 제거
- c := c.next
- node 반환
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
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:
def solve(self, node):
c = node
l = []
while c:
l.append(c.val)
c = c.next
c = node
while c and l:
c.val = l.pop()
c = c.next
if c == None:
break
c.val = l.pop(0)
c = c.next
return node
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
print_list(ob.solve(head))입력
[1,2,3,4,5,6,7,8,9]
출력
[9, 1, 8, 2, 7, 3, 6, 4, 5]
복잡도 분석
노드를 한 번 순회해 값을 모으고(O(n)), 다시 한 번 순회하며 값을 채우므로(O(n)) 시간 복잡도는 O(n)입니다. 값을 담는 보조 리스트에 O(n) 공간이 필요하므로 공간 복잡도 역시 O(n)입니다. 참고로 중간 지점을 찾은 뒤 뒤쪽 절반을 뒤집어 포인터만 교차 연결하면 O(1) 추가 공간으로도 같은 결과를 얻을 수 있습니다.