Swap Nodes in Pairs (Linked List)

LeetCode의 Swap Nodes in Pairs 문제다.

Swap Nodes in Pairs - LeetCode

연결 리스트로 주어진 노드를 2개씩 swap, 즉 서로 위치를 바꾸는 것이 문제의 목적이다. 예를 들어 노드가 1 -> 2 -> 3 -> 4처럼 주어진 연결 리스트가 있을 때 2 -> 1 -> 4 -> 3처럼 한 쌍씩 바꿔야 하며 만약 홀수개의 노드만 있다면 바꾸지 않는다. 즉 1 -> 2 -> 3 은 2 -> 1 -> 3처럼 바뀐다.

 

가장 먼저 생각할 수 있는 방법은 그냥 노드를 두 개씩 탐색하면서 서로 값을 교환하는 방법이다.

while currentNode and currentNode.next:
    currentNode.val, currentNode.next.val = currentNode.next.val, currentNode.val
    currentNode = currentNode.next.next
...

이런 풀이는 문제를 해결할 수는 있지만 문제를 잘 풀었다고는 하기 어려운데 왜냐면 이런 풀이는 연결 리스트의 특성을 거의 활용하지 못한, 연결 리스트뿐 아니라 배열에도 적용할 수 있는 풀이기 때문이다.

 

단순하게 두 노드의 값을 교환하는 풀이는 각 노드가 다루는 데이터가 커질수록 그 부담도 증가한다. 예를 들어 단순히 숫자 값만 갖는 노드가 아니라 리스트나 문자열 등 여러 가지 데이터를 포함하는 노드의 값을 교환하려면 일일이 필드를 참조해서 교환해줘야 하고 그 비용도 증가할 것이다.

 

그 대신 연결 리스트(이번 문제에서는 단방향 연결 리스트)에서 다음 노드를 가리키는 포인터를 교체하는 방식으로 교환한다면 실제로 노드의 값을 통째로 교환할 필요 없이 노드의 위치를 바꿀 수 있다. 그림으로 나타내면 다음과 같은 차이가 있다.

 

척 보기에도 포인터를 교체하는 작업이 더 부담이 적고 빠른 것을 볼 수 있다. 이처럼 연결 리스트에서는 노드의 값을 통째로 교환하는 것보다는 '연결'이라는 특성(포인터)을 적극 활용하는 것이 바람직한 풀이일 것이다.

 

그리고 위의 그림에서는 나타나지 않았지만 4개 이상의 노드가 있을 경우 1 -> 2 -> 3 -> 4는 2 -> 1 -> 4 -> 3이 되어야 한다. 이때 첫 번째 노드가 4번째 노드를 가리키게 되는 것을 볼 수 있다. 위의 그림처럼 단순히 한 쌍의 노드에서 첫 번째 노드가 다음다음 노드를 가리키고 두 번째 노드가 첫 번째 노드를 가리키도록 구현한다면 무슨 문제가 발생할까?

 

먼저 4개의 노드가 있다고 할 때 첫 번째 쌍의 노드를 교환하면 2 -> 1 -> 3 -> 4처럼 가리키게 된다. 그런데 이제 두 번째 쌍, 즉 세 번째 노드와 네 번째 노드를 치환할 때 문제가 발생하는데 한 쌍의 노드 중 첫 번째 노드는 다음다음 노드를, 즉 세 번째 노드는 null 노드를 가리키고 두 번째 노드는 첫 번째 노드를, 즉 네 번째 노드는 세 번째 노드를 가리키게 된다.

즉 위의 그림처럼 노드를 가리키게 되는 것인데 이 경우 2 -> 1 -> 3 까지만 접근할 수 있고 마지막 네 번째 노드는 가리키는 노드가 없기 때문에 접근할 수 없는 문제가 발생한다. 그렇기 때문에 이전에 치환한 한 쌍의 노드 중 두 번째 노드(치환되기 이전의 첫 번째 노드)를 기억하고 있다가 다음 한 쌍의 노드를 치환할 때 이전 노드에서 현재 치환된 첫 번째 노드를 가리키도록 이어줘야 한다. 단방향 연결 리스트기 때문에 이전 노드의 관점에서만 연결을 재설정해주면 된다.

 

이를 기반으로 작성한 코드는 다음과 같다.

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        result = head.next
        prev = None
        
        while head and head.next:
            nextNode = head.next
            nextNode.next, head.next = head, nextNode.next
            
            if prev:
                prev.next = nextNode
                
            prev = head
            head = head.next
        
        return result

나쁘지 않은 결과를 얻을 수 있었다.

 

 

이번 문제에 대한 내용을 읽으면서 느낀 건 그냥 문제를 푼다고 해서 나중에 면접 때 해당 알고리즘을 사용한 이유는 무엇인지, 그것 말고 다른 풀이는 없는지 물어볼 수도 있겠다는 것이다. 맨 처음 풀이처럼 그냥 값끼리 뒤집으면 풀 수는 있겠지만 문제에서 요구하는 연결 리스트의 특성을 활용하는 풀이를 작성할 수 있는지, 즉 문제의 본질을 알아챌 수 있는지 역시 중요할 것 같다.