[LeetCode] 24. Swap Nodes in Pairs

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

연결된 목록이 주어지면 인접한 두 노드를 모두 교체하고 헤드를 반환합니다.

✍️ 풀이

---

차분히 원래 인접하는 노드끼리의 연결 대신 새로운 연결을 해줘야한다.
1. root와 prev의 시작지점을 생성한다. [ListNode(None)]
2. 인접한 두 노드를 스왑하므로 최소한 현재노드와 다음노드가 존재해야만 한다.
3. 두번째 노드.next(세번째노드)를 첫번째노드.next가 가르키게 한다.
4. 그리고 두번째 노드.next는 첫번째노드를 가르키게 되어 두 노드의 위치가 바뀐다.
5. 이제 남은 첫번째 노드 앞에 있는 노드가 원래 두번째노드 였던 것을 가르키게 만든다.

모두 완료하면 두 노드가 스왑이 된다.

🛠 코드

---

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode(None)
        prev.next = head
        
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            
            prev.next = b
            
            head = head.next
            prev = prev.next.next
        return root.next

---

📝 정리

---

🎈 참고

---

Book 링크