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

(17) 페어의 노드 스왑 

★★ Normal

 

[LeetCode]

leetcode.com/problems/swap-nodes-in-pairs/

 

---

풀이법

 1. 단순 swap

이게 왜 노말인지 모르겠다. 처음에 easy가 훨씬 더 어려웠다. 연결리스트를 그 때 처음 다뤄서 그런건가?

 

PYTHON

 

onlybooks/algorithm-interview

 

JAVA

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode cur = head;
        
        while(cur!=null && cur.next !=null){
            int tmp = cur.val;
            cur.val = cur.next.val;
            cur.next.val = tmp;
            cur = cur.next.next;
        }
        return head;
        
    }
}

 

 

2. 반복 구조로 스왑

음.. 1번 방법은 면접관이 안된다고 할 수도 있다고한다.  그래서 실제로 .next를 노드를 가르키게 구조적으로 바꿀 필요가 있다.

원래 처음에 이 생각을 했는데, 1번 풀이보고 와! 그러네 val값만 변경하면 되는데 !! 이러고 띠용했는데.. 다시 반전이다 띠용? 🧐

 

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        
        root = prev = ListNode()
        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

 

3. 재귀

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