연결 리스트가 하나 주어지고, 두 개의 인덱스 값 i와 j가 함께 주어진다고 가정해 보겠습니다. 이때 해야 할 일은 리스트의 i번째 노드부터 j번째 노드까지 해당하는 구간만 골라 순서를 거꾸로 뒤집고, 그 결과로 완성된 리스트를 반환하는 것입니다. (인덱스는 0부터 시작한다고 가정합니다.)
예를 들어 입력이 [1,2,3,4,5,6,7,8,9]이고 i = 2, j = 6이라면, 인덱스 2부터 6까지의 노드들(값 3, 4, 5, 6, 7)이 뒤집혀 최종 출력은 [1, 2, 7, 6, 5, 4, 3, 8, 9]가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- 더미 헤드 노드 생성: prev_head := 값이 None인 새로운 연결 리스트 노드를 만들고, 이 노드가 원래 리스트의 첫 번째 노드를 가리키도록 설정합니다. 더미 노드를 활용하면 첫 번째 노드부터 뒤집는 경우에도 별도의 경계 조건 처리 없이 깔끔하게 구현할 수 있습니다.
- prev := prev_head, curr := node로 초기화합니다.
- 뒤집기 시작 지점 찾기: 0부터 i번까지 반복하면서 prev := curr, curr := curr.next로 두 포인터를 한 칸씩 앞으로 이동시킵니다.
- 반복이 끝나면 rev_before := prev, rev_end := curr로 설정합니다. 여기서 rev_before는 뒤집힐 구간 바로 앞 노드, rev_end는 뒤집힐 구간의 첫 번째 노드입니다.
- 구간 뒤집기: 총 (j - i + 1)번 반복하면서 다음 작업을 수행합니다.
- tmp := curr.next (다음 노드를 미리 저장)
- curr.next := prev (포인터 방향을 뒤집음)
- prev, curr := curr, tmp (두 포인터를 한 칸씩 앞으로 이동)
- 구간 재연결: rev_before.next := prev, rev_end.next := curr로 설정하여 뒤집힌 구간을 원래 리스트에 다시 연결합니다.
- 마지막으로 prev_head.next를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다:
예제 코드
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, i, j):
prev_head = ListNode(None, node)
prev, curr = prev_head, node
for _ in range(i):
prev, curr = curr, curr.next
rev_before, rev_end = prev, curr
for _ in range(j - i + 1):
tmp = curr.next
curr.next = prev
prev, curr = curr, tmp
rev_before.next, rev_end.next = prev, curr
return prev_head.next
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
i = 2
j = 6
print_list(ob.solve(head, i, j))
입력
[1,2,3,4,5,6,7,8,9], 2, 6
출력
[1, 2, 7, 6, 5, 4, 3, 8, 9]