연결 리스트(Linked List) 부분 뒤집기(reverse)

주어진 연결 리스트에서 일부분을 뒤집는 문제를 생각해보자. 연결 리스트에 [1, 2, 3, 4, 5]라는 값이 들어있고 2번째부터 4번째 사이를 뒤집는다고 하면, [1, 4, 3, 2, 5]가 된다. 연결 리스트 전체 뒤집기 문제보다 조금 더 생각할 거리가 있다.

전체 뒤집기와 다른 점은 뒤집기 경계에 있는 노드 정보를 기억해야 한다는 점이다. 뒤집기 부분 바로 직전 노드를 A라고 하고, 뒤집기 부분이 시작되는 노드를 B라고 하자. 그리고 뒤집기 부분이 끝나는 노드를 C라고 하자. 그러면 다음과 같이 처리해야 한다. 물론, 뒤집기 부분을 뒤집는 방법은 연결 리스트 전체 뒤집기와 같은 방법으로 처리해야 한다.

A.next = C
B.next = C.next

[1, 2, 3, 4, 5]의 예로 돌아가 보자. 뒤집기 부분은 [2, 3, 4]이다.  현재 노드가 가리키는 다음 노드가 현재 노드를 가리켰던 이전 노드가 되도록 하면 된다. (1) A노드는 1이므로 C노드인 4를 가리켜야 한다. (2) B노드는 2이므로 C노드의 next 노드인 5를 가리켜야 한다.

Before: 1[A] -> 2[B] -> 3 -> 4[C] -> 5
After: 1[A] -> 4[C] -> 3 -> 2[B] -> 5

개념은 위와 같다. 한 가지 주의해야 할 점은 뒤집기 부분이 첫 노드부터면 A노드가 실제로 존재하지 않고 head가 직접 C를 가리키게 해야 한다. 따라서 head가 C를 직접 가리키거나 A.next가 C가 되게 해야 한다. 이때 인자로 넘어온 head 값을 변경하기 위해서 포인터의 포인터를 사용해야 한다.

void reverseBetween(ListNode** head, int m, int n) {
	ListNode* cur = *head, *prev = *head, *start = NULL, **end = head;

	for (int i = 1; i < m; i++) {
		end = (ListNode**)&(cur->next);
		prev = cur;
		cur = cur->next;
	}
	start = cur;

	for (int i = m; i <= n; i++) {
		ListNode* nextnode = cur->next;
		cur->next = prev;
		prev = cur;
		cur = nextnode;		
	}
	start->next = cur;
	*end = prev;
}

풀기도 쉽지 않았는데, 설명하기는 더 어렵다.