[리트코드] Swap Nodes in Pairs(python)

리트코드, Swap Nodes in Pairs_인접 노드 바꾸기

 

TL;DR

• 연결리스트(LinkedList)를 활용할 수 있는지

문제 분석

1. 주어진 연결 리스트에 대해서 인접한 노드들을 바꾸고, 바뀐 연결 리스트를 반환한다.
2. 각 노드의 값을 바꾸어 문제를 해결하면 안 된다.

 

- 1 : 해결해야 하는 문제에 대해서 설명하고 있다. 노드들을 둘씩 짝지어 짝지은 노드를 서로 바꾼 연결리스트를 반환해야 한다.

- 2 : 제한조건이다. 연결리스트의 노드가 갖고 있는 값을 바꾸어 문제를 해결하면 안 된다.

입출력 형태

입출력 예시

 

- 주어진 연결리스트의 노드를 짝지으면 1 - 2, 3 - 4와 같이 짝을 지을 수 있다.

- 짝지은 노드들을 맞바꾼 연결리스트를 반환하면 된다.

풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head:
            return None
            
        root = prev = ListNode(None) # 1
        prev.next = head
        
        while head and head.next: # 2
            tmp = head.next
            head.next = tmp.next
            tmp.next = head
            
            prev.next = tmp
            
            head = head.next
            prev = prev.next.next
            
        return root.next

 

- 우선, 비어있는 연결리스트에 대해서 예외처리 코드를 집어넣었다. 넣지 않아도 무방하다.

- 1 : 정렬된 연결리스트를 할당할 root와 root에 정렬된 연결리스트를 집어넣을 일종의 포인터 역할을 할 prev를 선언한다.

- 2 : head를 조회하며 임시 연결리스트를 할당하여 swap 과정을 거친다. 예시를 통해 살펴보면 아래와 같다.

   - 첫 번째 while문 순회

     - tmp : 2 -> 3 - > 4, head : 1 -> 2 -> 3 -> 4

     - head : 1 -> 3 -> 4

     - tmp : 2 - > 1 -> 3 -> 4

     - root & prev : None -> 2 -> 1 -> 3 -> 4

     - head : 3 -> 4

     - prev : 1 -> 3 -> 4

   - 두 번째 while문 순회

    - tmp : 4, head : 3 -> 4

    - head : 3 -> None

    - tmp : 4 -> 3

    - root : None -> 2 -> 1(prev) -> 4 -> 3

    - head : None

    - prev : None

- tmp에 head의 next를 넣어 바꿀 값이 먼저 오도록 만든 후, head의 next를 tmp의 next로 할당하여 바꾼 노드를 제거한다.

- 이후 head를 tmp의 next로 할당하는 과정의 반복을 통해 두 연결리스트를 바꿀 수 있다.

- 이미 바꾼 원소는 다시 바꿀 필요가 없으므로 다음 과정에서 prev는 prev.next.next를 가르키게 된다.

- root와 prev는 같은 연결리스트로, prev가 root 연결리스트를 움직이며 바꾸는 과정을 담당한다.

- root의 head가 None을 갖고 있으므로 next를 반환한다.