[리트코드] 24. Swap Nodes in Pairs

# 문제 설명

주어진 연결리스트에 대해서, 2개의 인접한 노드들을 swap한 연결리스트를 반환해라.

 

# 입출력 예시

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

 

# 코드 풀이 1. 값만 바꾸기

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        now = head
        while now and now.next: # 값만 바꾸기
            now.val, now.next.val = now.next.val, now.val # swap
            now = now.next.next
        return head

 

# 코드 풀이 2. 반복으로 풀이

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root = now = ListNode()
        now.next = head # now는 head이전노드
        while head and head.next:
        	b = head.next # b는 head.next
            head.next = b.next # 다음다음노드
            b.next = head # b다음은 head
            now.next = b # now는 b를 가리킴
            
            head = head.next
            now = now.next.next # 다음다음노드
        return root.next

 

# 코드 풀이 3. 재귀로 풀이

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        while head and head.next:
            p = head.next
            head.next = self.swapPairs(p.next) # 다음다음노드 수행
            p.next = head
            return p # swap한 Pair반환
        return head

 

# 핵심 포인트

• 연결리스트의 두 노드를 swap한다는 것은 탐색하고 있는 now.next를 본 후 now를 본다는 것이다.
• head는 계속 탐색을 진행해나가고, now는 b를 따라 swap한 경로를 지나간다. 또는 p가 그렇게 지나간다.