Leetcode recursion (재귀): Swap Nodes in Pair 파이썬 풀이

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Swap Nodes in Pairs
등급: Medium

머리 아파지기 전 힐링

<코드>

어떻게 풀어야할까.

 

Recursion을 공부하면서 나온 문제니까, recursive function으로 풀어야 할 텐데..

 

Guideline으로 적혀있는 것은:

1. 첫 두 개의 노드를 바꾼다 (head and head.next)

2. swap(head.next.next)를 계속 불러서 list의 전체의 노드들의 value가 바뀌도록 한다.

3. 그런 다음 새로운 list의 head를 반환한다.

 

처음 step은 문제가 없다. (일 줄 알았는데) 이것도 어려웠다. 

1) 우선 head.next, 첫 번째 노드를 세 번째 노드로 포인트 했다.

2) 다음, head를 두 번째 노드를 바라보게 하였다. 

3) 마지막으로, 두 번째 노드는 첫 번째를 포인트 하게 했다. 

이 와중에 처음에는 a= head.next, b= head, 이렇게 두 varaible를 만들게 되었다.

 

그런데 2번을 어떻게 해야 하나... 아니, 2번은 가능할 것 같긴 한데, 그러면 어떻게 처음의 head를 반환할 수 있는지가 헷갈렸다. 아니, 몰랐다.

 

다른 function을 만들면 되지 않을까?라는 생각이 들었다.

 

그래서 했는데, 문제는 이제 어떤 경우에는 코드가 작동하지 않게 해야 하는 것인가..

지금까지 적은 것...

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        newhead = head
        headtoreturn = head.next
        while newhead:
            newhead = self.swap(newhead)
        
        return headtoreturn
    
    def swap(self, head):
        if head.val and head.next.val:            
            # first node to see third node 
            # (store head.next so we do not lose the pointer to the 2nd node)
            a = head.next
            head.next = head.next.next
            
            # head to see 2nd
            b = head
            head = a
            
            #2nd node to point the first node
            head.next = b
            
            return head.next.next
        
        return None

 

아, 그럼 '4'가 계속 없어서 바꾼 것:

그 이유는, 그 전의 두 번째 노드의 .next, 포인터가 바뀌지 않기 때문에 바꿔보았다.

class Solution(object):
    def swapPairs(self, head):
        if head.val and head.next.val:            
            # first node to see third node 
            # (store head.next so we do not lose the pointer to the 2nd node)
            a = head.next
            head.next = head.next.next
            
            # head to see 2nd
            b = head
            head = a
            
            #2nd node to point the first node
            head.next = b
        
        newhead = head.next
        
        while newhead.next:
            newhead = self.swap(newhead)
        
        return head
    
    def swap(self, head):
        if head.val and head.next.val:            
            # first node to see third node 
            # (store head.next so we do not lose the pointer to the 2nd node)
            a = head.next.next
            head.next.next = head.next.next.next
            
            # head to see 2nd
            b = head.next
            head.next = a
            
            #2nd node to point the first node
            head.next = b
            
            return head.next
        
        return None

결론: 둘 다 안된다... 너무한 것 아니냐고 ㅠㅠ 애초에 이걸 recursive이라고 하지는 못할 것 같다. 이것도 마찬가지로 바꾸지는 못했다...

 

그래서 결국에는 discussion을 보게 되었다.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next: 
            return head
        
        # a dummy node // 
        dummy = ListNode(0)
        #point to the first node
        dummy.next = head
        # so that the cur node is always the node before the nodes that must change
        cur = dummy
        
        while cur.next and cur.next.next:
            # the first node
            first = cur.next
            # the second node
            sec = cur.next.next
            # (1) the current node to point to the second node
            cur.next = sec
            # (2) the first node to point to the third node
            first.next = sec.next
            # (3) so the second node point to the first node and swap nodes
            sec.next = first
            # so that it points to the new "first" node (eq. second node or the node before the 2 nodes that must switch)
            cur = cur.next.next
        
        return dummy.next     
        
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # modified from
        # https://leetcode.com/explore/learn/card/recursion-i/250/principle-of-recursion/1681/discuss/171788/Python-or-Dummynode

와우.. 멋지다. 내가 생각한 것의 그래도 본질은 틀리지 않아서 다행이다...

 

하지만 이 recursion solution은 생각도 못했다. 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:
            return head
        # keep the third node pointer
        new_start = head.next.next
        # head to look at the 2nd node, 2nd node to point to the first node
        head, head.next = head.next, head
        # point the first node into the third node (recursively)
        # this recursive will eventually return head by the if statement above, and give the third node pointer, new_start!
        head.next.next = self.swapPairs(new_start)
        return head

멋지다...

 

<총평>

괜히 medium이 아니다..

 

Happy coding!

Swap Nodes in Pairs - LeetCode