[파이썬 알고리즘] 페어의 연결 리스트 노드 스왑

페어의 연결 리스트 노드 스왑

리트코드로 풀러 가기

연결 리스트를 입력받아 페어 단위로 스왑하라.

입력
1 -> 2 -> 3 -> 4

출력
2 -> 1 -> 4 -> 3

---

직관적인 풀이

직관적으로 생각해서 노드 자체를 스왑하지 말고, 노드의 값들을 바꿔주는 풀이가 가능하다.

def swapPairs(self, head):

    if not (head and head.next):
        return head

    node = head
    while node and node.next:
        node.val, node.next.val = node.next.val, node.val
        node = node.next.next

    return head

input에 대한 예외체크를 하면서, 각 노드들의 페어끼리 값을 스왑한다.

반복 구조의 스왑

하지만, 이 문제의 의도는 위와 같이 값만 바꾸는것이 아닐것이다.

노드 끼리의 스왑은 값만 변경할 때와 같지만, 노드 끼리의 스왑을 하고 난 뒤, 지난 스왑의 마지막 노드와 스왑된 결괏값을 연결해 주어야 한다.

그 과정을 코드에 추가한 뒤, 첫 스왑에서 이용할 prev를 선언한다.

해당 결과를 코드로 옮기면 다음과 같다.

def swapPairs(self, head):
    root_node = prev = ListNode(None)
    prev.next = head
    current_node = head
    
    while current_node and current_node.next:
        next_node = current_node.next
        current_node.next = next_node.next
        next_node.next = current_node
        
        prev.next = next_node
        
        current_node = current_node.next
        prev = prev.next.next
        
    return root_node.next

재귀 구조의 스왑

스왑을 한 결과의 첫 노드 ( 1 -> 2를 스왑한다면 2 -> 1로 스왑한 뒤, 2)를 리턴하게 한 뒤,

이 과정들을 재귀 형태로 묶으면 아래와 같은 풀이를 할 수 있다.

def swapPairs(self, head):
    if head and head.next:
        p = head.next
        
        head.next = self.swapPairs(p.next)
        p.next = head
        return p
    
    return head

위의 반복 구조와 비교했을 때, root_node를와 prev를 사용하지 않아도 되어서 공간 복잡도가 낮고, 코드 또한 깔끔하다.