17. Swap Nodes in Pairs

🎯 leetcode - 24. Swap Nodes in Pairs

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 17번 문제

📌 날짜

2020.01.25

📌 시도 횟수

1 try

💡 Code

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        i = 0
        prev = None
        root = node = ListNode(0)
        while head:
            i += 1
            if i % 2 == 0:
                node.next = ListNode(head.val)
                node = node.next
                node.next = ListNode(prev.val)
                node = node.next
            prev, head = head, head.next
        if prev and i % 2 != 0:
            node.next = ListNode(prev.val)
        return root.next

💡 문제 해결 방법

- 변수 i를 만들었다. i는 짝수 번째 연결리스트 노드를 방문했을 때 2로 나누어 떨어지는 성질을 갖는다.
- i = 0에 대하여 i가 짝수일 때 head, prev를 스왑하여 새로운 연결 리스트에 저장한다.
- 만약 숫자의 개수가 홀수개이면, while문 밖에서 따로 추가해주었다.
>>>   if prev and i % 2 != 0:
>>>       node.next = ListNode(prev.val)

💡 새롭게 알게 된 점

Q. 새로운 연결 리스크를 만들지 않고 내부적으로 스왑할 수는 없을까?

❌ (한번에 맞추지 못한 경우) 오답의 원인

---

😉 다른 풀이

📌 하나. 반복 구조로 스왑하기

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        root = prev = ListNode(0)
        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

💡 문제 해결 방법

• 아래 그림을 참고해서 이해하자.
  
  

💡 새롭게 알게 된 점

1. 일반적으로 연결리스트 node1->node2 를 스왑(node2->node1)하는 방법
*(초기 head = node1)라고 가정
>> b = head.next
>> head.next = b.next (뒤의 노드들과 연결)
>> b.next = head (역방향 연결)

2. 하지만 위의 경우는 2개 노드 이상의 연결리스트이므로 prev(앞)노드도 고려해야 됨
>> prev.next = b

3. 다시 다음번 head, prev에 대하여 반복적으로 수행하기 위해 이동
>> head = head.next
>> prev = prev.next.next

---

📌 둘. 값만 교환하기

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        curr = head
        while curr and curr.next:
            curr.val, curr.next.val = curr.next.val, curr.val
            curr = curr.next.next
        return head

💡 새롭게 알게 된 점

- 연결리스트도 값만 교환하는 게 가능하구나

---

📌 셋. 재귀로 스왑 🤯

class Solution:
    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

💡 문제 해결 방법

- 재귀를 한번 돌떄마다 head는 홀수번째 노드를 가리키고, p는 짝수번째 노드를 가리킨다.
* 예를 들어 1 -> 2 -> 3 -> 4 라는 연결리스트가 있다고 가정하자.
- 첫번쨰 재귀에서는 head = 1, p = 2 / 두번째 재귀에서는 head = 3, p = 4)
- 만약 더이상 head(or head.next)가 존재하지 않으면 차례대로 리턴한다.
- 리턴할 때는 p.next = head 를 통해 역순으로 연결을 한다.
- 그리고 p를 리턴함으로 다시 (현재)head.next = (이전)p 가 되도록 한다.
- 즉 첫번째 리턴할 때는 4 -> 3이 연결되고, 1 -> 4로 연결이 되어 최종적으로 1 -> 4 -> 3이 연결이 된다.
- 두번째 리턴할 때는 2 -> 1이 연결되고, 최종적으로 return p(값이 2인 노드)가 리턴된다.
- 따라서 최종 리턴된 p를 기준으로 연결리스트를 출력해보면 2 -> 1 -> 4 -> 3이 되는 것이다~

💡 새롭게 알게 된 점

으아아 재귀 너무 어렵다ㅠ
계속계속 봐서 익숙해져야겠다..

🍡머리로는 이해가 잘 안되니까 그림으로 보자!👀