def first(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    node_curr = head
    # 1. 반복: 두 개씩 스왑하므로, 현재의 다음 노드가 있는 동안 반복
    while node_curr.next:
        # 2. 노드의 스왑: 값만 바꾸면 되지 않을까?
        node_curr.val, node_curr.next.val = node_curr.next.val, node_curr.val
        # 3. 현재 노드는 다다음 노드로 변경
        if node_curr.next.next:
            node_curr = node_curr.next.next
        else:
            break

    return head

    # 실패
    def second(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        # 1. 반복: 두 개씩 스왑하므로, 현재의 다음 노드가 있는 동안 반복
        # ListNode는 Python Object로 같은 메모리 주소를 가리킨다(by reference)
        # node_curr에는 head에 대한 `주소` 저장
        node_curr = head
        while node_curr and node_curr.next:
            # 2. 스왑
            # - 현재 노드 임시 저장
            tmp = node_curr
            # - 다음 노드를 현재 노드로
            node_nnext = tmp.next.next
            node_curr = tmp.next
            # - `이전 현재 노드`를 다음 노드로
            node_curr.next = tmp
            # - `이전 다음 노드`의 다다음 노드가 있었다면, `현재 다음 노드`의 다음 노드로 치환
            node_curr.next.next = node_nnext
            node_curr = node_curr.next.next

        return head

def third(self, head: ListNode) -> ListNode:
    # root: 풀이에서 head가 계속 변경되므로, root.next로 결과 값을 반환한다
    # prev: 다음 비교를 위해 두 칸씩 이동시킬 변수
    root = prev = ListNode(None, head)

    # head = 1 -> 2 -> 3 -> 4
    # root: None -> 1 -> 2 -> 3 -> 4
    # prev: None -> 1 -> 2 -> 3 -> 4
    while head and head.next:
        # tmp: 값이 실제로 스왑되는 변수
        # 한 쌍에서 다음 노드를 앞으로 끌어 올린다
        # tmp = 2 -> 3 -> 4
        tmp = head.next
        # 다다음 노드를 원래 head의 다음 노드로 할당한다
        # tmp.next = 3 -> 4
        # head = 1 -> 3 -> 4
        head.next = tmp.next
        # 앞으로 끌어 올려진 `이전의 다음 노드`에 head를 붙인다
        # tmp.next = 1 -> 3 -> 4
        # tmp = 2 -> 1 -> 3 -> 4
        tmp.next = head

        # prev = None -> 1 -> 2 -> 3 -> 4
        # prev = None -> 2 -> 1 -> 3 -> 4
        prev.next = tmp

        # head = 3 -> 4
        head = head.next
        # prev = 1 -> 3 -> 4
        prev = prev.next.next

    return root.next

# 재귀 풀이 방식. 가장 끝에서부터 스왑하면서 올라온다
def fourth(self, head: ListNode) -> ListNode:
    # p = 2
    #   tmp = 4 -> 3 -> None
    #       head = 1 -> 4 -> 3 -> None
    #           p = 2 -> 1 -> 4 -> 3 -> None
    #  2 -> 1 -> 4 -> 3
    if head and head.next:
        # p는 우선 다음 값으로 할당하고
        p = head.next
        # 스왑된 값을 리턴 받는다
        tmp = self.fourth(p.next)
        # 스왑된 tmp를 head의 다음 값에 넣고
        head.next = tmp
        # 헤드를 앞서 스왑된 p의 다음 값에 넣는다
        p.next = head
        return p

    return head