[파이썬 알고리즘 인터뷰][연결리스트] 페어의 노드 스왑

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

연결 리스트를 페어 단위로 스왑

 

책에서 구현된 코드

def swapPairs(self, head: ListNode) -> ListNode:
    if head and head.next:
        p = head.next
        
        head.next = self.swapPairs(p.next)
        p.next = head
        return p
    return head

 

기억해야할 기법

• 반복되는 substruct에 대한 재귀 설계
  • node1 -> node2 -> node3 ...
  • node2가 node1을 가리킴
  • node1이 swap이 끝난 node3을 가리킴

 

내가 구현한 코드

    def swapPairs(self, head: ListNode) -> ListNode:
        root = ListNode(0)
        root.next = head
        pointer = root

        while pointer.next and pointer.next.next:
            left = pointer.next
            right = pointer.next.next
            pointer.next, right.next, left.next = right, left, right.next
            pointer = left

        return root.next

• 속도는 같지만 가독성 차이가 큼
• 재귀 설계 자체를 떠올리지 못함