설명
LeetCode의 Reverse Linked List II 문제다.
첫 번째 노드부터 마지막 노드까지 오름차순 값을 가진 노드들의 연결 리스트를 주어진 범위만큼 뒤집어서 반환하는 것이다. 예를 들어 노드 1, 노드 2, 노드 3, 노드 4, 노드 5가 있을 때 2번째 노드부터 4번째 노드까지 뒤집어서 반환하라고 하면 노드 1, 노드 4, 노드 3, 노드 2, 노드 5 순서로 바뀌어서 반환되어야 한다.
노드의 값이 오름차순으로 주어진다는 조건은 아마 연결 리스트가 잘 뒤집혔는지 확인하기 위한 수단인 것 같다.
풀이
생각해볼 수 있는 방법은 i 번째 노드부터 j 번째 노드까지 뒤집는다고 할 때 i-1 번째 노드가 j 번째 노드를 가리키고 i 번째 노드가 j+1 번째 노드를 가리키도록 구현하는 것이다. 위의 예제에서는 2(i) 번째 노드부터 4(j) 번째 노드까지 뒤집기 때문에 1(i-1) 번째 노드가 다음 노드로 4(j) 번째 노드를 가리키고 2(i) 번째 노드는 5(j+1) 번째 노드를 가리키게 된다.
이때 맨 처음 노드부터 뒤집는 경우(i=1) i-1(=0) 번째 노드는 존재하지 않을 수 있으므로 예외 처리가 필요하다. 그래서 맨 처음 노드부터 뒤집는다면 j 번째 노드를 반환하도록 처리해야 한다.
i 번째 노드부터 j 번째 노드까지 뒤집는 과정은 파이썬의 동시 할당을 이용하여 다음 노드가 이전 노드를 가리키도록 변경하면서 어렵지 않게 진행할 수 있다. 중요한 것은 노드를 뒤집는 것 자체보다는 뒤집힌 노드 주변의 노드들이 뒤집힌 노드들과 잘 연결될 수 있어야 한다는 것이다.
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
# 단 하나의 노드를 뒤집는 경우 별도의 작업이 필요하지 않음.
if left == right:
return head
# 뒤집힐 맨 왼쪽 노드의 이전 노드까지 탐색.
currentIndex = 1
originHead = head
leftBorderNode = None # i-1 번째 노드를 의미.
while currentIndex < left:
leftBorderNode = head
head = head.next
currentIndex += 1
# 인덱스 기반으로 탐색하기 때문에 현재 노드가 뒤집힐 노드의 왼쪽 노드.
leftNode = head
# 뒤집힐 노드의 오른쪽 노드까지 탐색하면서 연결 뒤집기.
prev = None
while currentIndex <= right:
# 현재 노드의 다음 노드(head.next)를 이전 노드(prev)로 설정.
# 현재 노드(head)는 다음 노드(head.next)로 이동.
# 이전 노드(prev)를 담는 변수에 현재 노드(head) 저장.
# 위 과정은 파이썬의 기능으로 전부 동시에 실행가능.
head.next, head, prev = prev, head.next, head
currentIndex += 1
# 맨 마지막 노드까지 뒤집었다면 prev는 맨 오른쪽(j번째) 노드를 가리킴.
rightNode = prev
# head 변수는 j+1 번째 노드를 가리키고 있을것.
rightBorderNode = head
# i 번째 노드의 다음 노드로 j+1 번째 노드를 설정.
leftNode.next = rightBorderNode
# i-1번째 노드는 존재하지 않을 수 있으니 예외처리.
# j 번째 노드를 다음 노드로 설정.
if leftBorderNode:
leftBorderNode.next = rightNode
# 만약 존재하지 않는다면 처음 노드부터 뒤집은 것.
# 뒤집은 후 첫번째 노드가 되는 j 번째 노드를 반환.
else:
return rightNode
# 처음에 저장해뒀던 첫번째 노드를 반환.
return originHead후기
파이썬의 동시 할당을 이용하여 한결 깔끔하게 풀 수 있었던 문제였던 것 같다. 연결 리스트로 주어진 노드들에서 인덱스를 이용하여 뒤집을 범위를 찾아야 했기 때문에 왼쪽 끝, 오른쪽 끝 노드를 탐색하는 과정이 좀 지저분한데 좀 더 파이토닉(pythonic)한 방법이 있을지 고민해봐야겠다.
