[코테] 리트코드 연결 리스트 24. Swap Nodes in Pairs

24. Swap Nodes in Pairs

문제 링크

https://leetcode.com/problems/swap-nodes-in-pairs/description/

문제 설명

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

제한 사항

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

입출력 예 #1

1. Input: head = [1,2,3,4]
2. Output: [2,1,4,3]

입출력 예 #2

1. Input: head = []
2. Output: []

입출력 예 #3

1. Input: head = [1]
2. Output: [1]

문제 풀이

1. 연결 리스트 구조를 바꾸는 것이 아닌 값만 바꾸는 방식
2. 반복 구조로 노드를 바꾸는 방식
3. 재귀 구조로 노드를 바꾸는 방식

## 값만 교환
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head

    while cur and cur.next :
        # 값만 교환
        cur.val, cur.next.val = cur.next.val, cur.val
        cur.next.next

    return head

## 반복 구조로 스왑
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root = prev = ListNode(None)
        prev.next = head

        while head and head.next:
            # b가 a(head)를 가리키도록 할당
            b = head.next
            head.next = b.next
            b.next = head

            # prev가 b를 기리키도록 할당
            prev.next = b

            # 다음번 비교를 위해 이동
            head = head.next
            prev = prev.next.next
        
        return root.next

## 재귀 구조로 스왑
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            p = head.next
            # 스왑된 값 리턴 받음
            head.next = self.swapParis(p.next)
            p.next = head
            return p
        return head