Reverse Linked List (Linked List)

LeetCode의 Reverse Linked List 문제다.

Reverse Linked List - LeetCode

단방향 연결 리스트를 뒤집는 기능을 구현하는 문제다. 별로 어려운 문제는 아닌데 다음처럼 파이썬의 다중 할당(multiple assignment)을 사용해서 간단하게 풀 수 있어서 포스팅으로 남긴다.

class Solution:    
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        
        previousNode = None
        while head:
            head.next, previousNode, head = previousNode, head, head.next
            
        return previousNode

3개의 변수를 한 번에 다중 할당하고 있기 때문에 좀 헷갈릴 수도 있는데 1 -> 2 -> 3 -> 4처럼 연결된 노드를 노드 1부터 탐색하면서 (X) <- 1 <- 2 <- 3 <- 4처럼 뒤집는 과정이다. 이전 노드(previousNode)는 첫 노드에서는 존재하지 않기 때문에 None((X)로 나타냄)으로 설정해두고 시작한다.

 

먼저 head.next를 보자. 이는 현재 노드의 다음 노드를 가리키는 필드로 리스트를 뒤집으려면 이전 노드를 가리켜야 한다. 그러나 단방향 연결 리스트기 때문에 이전 노드를 참조할 수 있는 방법이 없다. 그러므로 이전 노드를 기억하는 previousNode 변수가 필요한 것이다. 어쨌든 이전 노드를 가리키기 위해 head.next는 previousNode 변수로 할당된다. 첫 번째 노드라면 previousNode는 None이므로 None을 가리키게 될 것이며 이는 1 -> 2에서 (X) <- 1 <- 2의 (X)에 해당한다.

 

다음으로 previousNode는 head로 할당된다. 1 -> 2에서 노드 2가 노드 1을 가리키려면 노드 1이 미리 저장되어 있어야 하기 때문에 현재 노드를 이전 노드 변수에 저장하는 것이다. 이후 노드 2로 이동했을 때 previousNode에는 노드 1이 저장되어 있기 때문에 위의 head.next에서 이 변수를 사용해서 이전 노드를 가리킬 수 있다.

 

마지막으로 head는 head.next를 할당하여 연결 리스트의 다음 노드로 이동한다. 그런데 이렇게 head와 previousNode가 섞여서 다중 할당되고 있는데 뭔가 꼬이거나 다른 곳을 가리키는 일은 발생하지 않는다. 왜 그럴까?

 

다중 할당이란 말은 생소하지만 파이썬의 장점으로 매일 언급되는 a, b = b, a도 다중 할당이다. 위처럼 여러 개의 변수를 한 번에 다중 할당할 수도 있는데 위의 코드처럼 이때 단순히 대입이 아니라 기존의 변수를 계산하여 더하면서 할당하면 어떻게 될까? 이 부분은 잘 모르고 있던 부분이었는데 이번 문제를 풀면서 각 변수마다 별개의 환경으로 생각할 수 있다는 것을 알게 되었다.

>>> a, b, c = 1, 2, 3
>>> a
1
>>> b
2
>>> c
3

예를 들어 다음처럼 변수 a, b, c에 각각 1, 2, 3이 등록되어 있다고 할 때 a, b, c를 c, b, a로 대입하면 생각하는 것처럼 각각 3, 2, 1이 된다.

>>> a, b, c = c, b, a
>>> a
3
>>> b
2
>>> c
1

그런데 c, b, a가 아니라 a+b, b+c, c+a처럼 대입하면 어떻게 될까? a, b, c는 각각 1, 2, 3이기 때문에 a+b, b+c, c+a는 1+2, 2+3, 3+1이 된다.

>>> a, b, c=1, 2, 3
>>> a, b, c=a+b, b+c, c+a
>>> a
3
>>> b
5
>>> c
4

대입 연산자는 오른쪽에서 왼쪽으로 동작하기 때문에 c에는 c+a가 저장되어 4가 되고 b에서 b+c에 c가 4로 할당됐으니 2+4가 된다고 생각할 수도 있다. 그러나 파이썬의 다중 할당 환경에서는 오른쪽의 할당 표현식을 왼쪽보다 우선하여 처리한다. 즉 a, b, c에 각각 a+b, b+c, c+a를 저장할 때 c먼저 c+a를 계산하고 b에 b+c를 계산하고 이렇게 순서대로 하는 게 아니라 a+b, b+c, c+a를 미리 계산한 후에 각각 a, b, c에 대입하는 것이다.

 

그래서 위의 풀이에서 'head.next, previousNode, head = previousNode, head, head.next'처럼 다중 할당했을 때 오른쪽의 previousNode, head, head.next는 각각 따로 할당된 것처럼 head.next, previousNode, head로 할당된 것이다. 그럼 이 할당을 각각 분리해서 실행해보면 어떨까?

>>> a, b, c = 1, 2, 3
>>> a = a + b
>>> b = b + c
>>> c = c + a
>>> a
3
>>> b
5
>>> c
6

위와는 달리 3, 5, 6으로 c+a가 6으로 계산된 것을 볼 수 있다. 이는 다중 할당처럼 동시에 할당한 게 아니라 a부터 순차적으로 할당했기 때문에 다른 결과가 나오는 것이다. 이렇듯 다중 할당은 단순히 여러 줄의 표현식을 한 줄로 합친 게 아니라 각 표현식의 콘텍스트를 독립적으로 유지할 수 있다는 장점이 있으니 자주 활용해야 할 것이다.

 

 

[참고 | stackoverflow.com/questions/8725673/multiple-assignment-and-evaluation-order-in-python]