역순 연결 리스트 Ⅱ
문제
인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.
입력
1→2→3→4→5→NULL, m = 2, n = 4
출력
1→4→3→2→5→NULL
코드
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
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
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
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)
l1.next.next.next.next= ListNode(5)
l1.next.next.next.next.next = ListNode(None)
Solution().reverseBetween(l1, 2, 5)
풀이
start는 변경이 필요한 2의 바로 앞 지점인 1을 가리키게 하고 end는 start.next인 2로 지정한다. 그리고 head는 1인데, 그보다도 더 앞에 root를 만들어 head보다 이전에 위치시킨다. 나중에는 root.next를 최종 결과로 리턴하게 될 것이다.
이렇게 할당된 start와 end는 끝까지 변하지 않는다. 즉 1과 2로 마지막까지 유지되며, start와 end를 기준으로 반복하면서 역순으로 뒤집는다.
이 그림에서 2)부터가 반복하며 진행되는 부분이다. start.next를 tmp로 지정하고, start.next는 end.next가 된다. 그리고 end.next는 end.next.next로 한 칸 더 앞의 값을 끌어온다. 그리고 start.next.next를 tmp로 지정한다. 즉 이전에 start.next였던 노드를 배치하는 것과 동일하다.
다중할당 2번째 부분에서 start.next가 end.next를 가리키게 되어 기존의 start.next가 사라짐으로 먼저 tmp에 저장하고 나중에 start.next.next에 기존 start.next(tmp)를 엮어준다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]