“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/reverse-linked-list-ii/
연결 리스트의 인덱스 left부터 right까지를 역순으로 만드는 문제다. [1,2,3,4,5], left=2, right=4 라면 [1,4,3,2,5] 가 답이다.
이번에는 억지스런 방법이라도 떠오르지 않았다. 인덱스 범위의 노드를 따로 떼서 역순으로 바꿔 갖다 붙여야 하나?? 내힘으로 도전하려 했지만 술기운(…)에 귀찮아져 풀이를 참고하고 말았다. start, end, tmp 3개의 포인터를 쓴다는 것에 놀랐다. 생각의 확장이 대단하게 느껴진다.
- 첫 노드 앞에 None 노드를 만들어 root와 start 포인터로서 시작한다.
- 역순으로 바꿀 인덱스의 직전 노드가 start(1), 그 다음 노드가 end 포인터(2)가 되도록 한다.
- 다음을 역순으로 바꿀 인덱스 수만큼 반복한다.
tmp 포인터에 start.next를 저장해둔다.(tmp = 2)
start.next는 end.next(3)로 바꾼다.(start.next = 3)
end.next는 end.next.next(4)로 바꾼다.(end.next = 4)
start.next.next는 tmp(2)로 바꾼다.(start.next.next = 2)
def reverseBetween1(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
# 1
root = start = ListNode(None)
root.next = head
# 2
for _ in range(left - 1):
start = start.next
end = start.next
# 3
for _ in range(right - left):
tmp = start.next
start.next = end.next
end.next = end.next.next
start.next.next = tmp
return root.next누가 생각했는지는 모르겠지만 참 머리 좋다. 이쯤 되면 연결 리스트의 처리는 웬만해선 O(n)으로 되는 건가 싶다.