[알고리즘] 역순 연결 리스트 II

문제

인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

입력

1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4

출력

1 -> 4 -> 3 -> 2 -> 5 -> NULL

풀이 ( 반복 구조로 노드 뒤집기)

---

이 풀이에서는 start와 end변수를 이용하여 풀이할 수 있다. start와 end를 기준으로 반복하면서 역순으로 뒤집으면서 풀이할수 있다.

root = start = ListNode(None)
root.next = head

# start, end 지정
for _ in range(m - 1):
    start = start.next

end = start.next

여기서 start는 변경이 필요한 2의 바로 앞 지점인 1을 가르키게 하고 end는 start.next인 2를 지정한다. head는 1이고 root가 head를 가르키게 하여 최종적으로 root.next를 반환하게 된다.

그리고 start와 end는 끝까지 값이 변하지 않는다. 아래 코드는 start와 end를 기준으로 연결 리스트를 역순으로 바꾸는 역할을 한다. 위의 입력 예제로 코드와 함께 동작과정을 살펴보자.

tmp = start.next
start.next = end.next
end.next = end.next.next
start.next.next = tmp

1. start.next를 tmp로 지정한다.
2. start.next는 end.next가 된다.
3. end.next는 end.next.next로 한 칸 더 앞의 값을 가르킨다.
4. start.next.next 는 tmp로 지정한다.

위와 같은 구조로 n-m번 반복하면 최종결과가 나오게 된다.

반복하면서 역순으로 리스트를 구성할 때 다중 할당 형태로 코드를 구성할 수 있다.

def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
	  # 예외 처리
	  if not head or m == n:
	      return head
	
	  root = start = ListNode(None)
	  root.next = head

	  # start, end 지정
	  for _ in range(m - 1):
	      start = start.next
	  end = start.next
	
	  # 반복하면서 노드 차례대로 뒤집기
	  for _ in range(n - m):
	      tmp, start.next, end.next = start.next, end.next, end.next.next
	      start.next.next = tmp
	  return root.next

정리

---

반복문을 활용해서 연결 리스트를 역순으로 뒤집을 수 있고, 노드를 차례대로 뒤집을 때 다중 할당 구조를 사용하면 소스코드가 간결해지는 것을 볼 수 있었다.