24. Swap Nodes in Pairs

ListNode를 2개씩 짝지어서  swap하는 문제 

 

주의할 점은 

 

1) 두개씩 짝을 만든 ListNode가 있는지 확인(head, head.next가 None인지 아닌지 확인)

2) 주소값까지 확인하는것은 아닌거 같고, 값만 바꾸면 될것 같다.

 

 

- 값만 교환하는 경우 

    def swapPairs(self, head: ListNode) -> ListNode:
        cur = head

        while cur and cur.next:
            cur.val, cur.next.val = cur.next.val, cur.val
            cur = cur.next.next

        return head

- 리스트 자체를 교환하는 경우

리스트를 교환하려면 리스트가 가지고 있는 다음 값도 같이 교환해줘야된다. 

 

그림에서 3->4를 교환한다고 하면 3의 next를 4의 next로 바꿔야하고(1),

4의 next를 3으로 이어지게 만들어야한다. 

또한 이전 값이 있었다면, 2의 next를 4로 오도록 해야된다.

 

    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode(None)
        root.next = prev.next = head

        while head and head.next:
            # 3->4를 4->3으로 만들기
            cur = head.next
            head.next = cur.next
            cur.next = head

            # 3->4에서 3에 연결된 ListNode를 4로 바꿔주기(이전 ListNode)
            # 그리고 다음을 위해서 prev를 3으로 옮겨놓기
            prev.next = cur
            head = head.next
            prev = prev.next.next

        return root.next

 

- 재귀로 리스트를 분할하여 답을 구하는 경우 

예를 들어서 1->2->3->4가 있고, 1->2를 swap하는 경우에는 

먼저 p라는 임시 변수에 head.next, 즉 2를 넣어준다. 

그리고 현재 head.next값(1의 다음에 올 값)을 p.next 이후부터 구한다. (3->4...이후의 값들로만 구한다.)

 

마지막으로 p.next값을 head로 바꿔준다. 

 

    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