Leetcode: Reverse Linked List python 풀이

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

 

문제: Reverse Linked List
등급: Easy

내용: linked list를 reverse해야한다.

<코드>

처음 든 생각은, value를 바꾸는 것이었다. 그런데 그러려면 linked list를 array에 저장해서 해야 하는 방법밖에 없을 것 같아서 포기했다. array를 만든다면 linked list의 이점을 포기하는 것 아닌가. 

 

그렇다고 또 다른 linked list를 만들 수는 없지 않은가...

 

어떻게든 pointer를 바꿔서 해볼까 생각하고 있었다. 그런데 내 머리로는 도저히 안 되는 거였다.

 

그래서 오늘도! discussion을 보았다.

 

Discussion에서 한 글에 적혀 있는 솔루션은 너무나도 깔끔했다. 3 pointer를 활용하였다.

# 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 reverseList(self, head):
        # previous and current = None and head (it is like the dummy node in Swap Nodes in Pair)
        prev = None
        curr = head
        
        #while current is not null (till it reaches the end of the list)
        while curr:
            # next pointer pointing the next node so that we have the pointer to next node
            # even though we may turn the current node pointer to the previous one
            nex = curr.next
            # this is when we turn our curr node pointer to the previous one
            curr.next = prev
            # since we turned our current node pointer to previous, time to update to new previous node
            prev = curr
            # now new current node
            curr = nex
        
        return prev

prev, nex, 그리고 curr 포인터 세 개가 있다. prev는 그 전 node, nex는 그다음 node의 포인터들이다.

 

while loop안에서는, 

1. next pointer를 curr.next로 포인트 해준다.

2. 지금 curr node를 prev, 그 전 node로 포인터를 돌려준다.

3. previous node에 포인터는 이제 없어도 된다. 하지만, 이제 다음에 또 이렇게 하기 위해서 지금 prev= curr로 업데이트해줘야 한다.

4. curr = next 이제는 next node로 넘어간다. 이제 next가 curr가 되는 것이다.

반복한다.

 

Recursive은 도대체 모르겠어서 찾아봤다. 이런 코드가 있고

class Solution(object):
    def reverseList(self, head):
        return self._reverse(head)

    def _reverse(self, node, prev=None):
        if not node:
            return prev
        n = node.next
        node.next = prev
        return self._reverse(n, node)

이런 코드도 있었다:

class Solution(object):
    def reverseList(self, head):
        if not head or not head.next:
            return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return node
        # from a nice solution:
        # https://leetcode.com/explore/learn/card/recursion-i/251/
        # scenario-i-recurrence-relation/2378/discuss/246827/
        # Python-Iterative-and-Recursive

도대체 뭔 소리인가 싶어서 하나씩 살펴보았다.

 

그랬더니, 우선 node = self.reverseList(head.next)는 계속 recursive call을 해준다. 마지막에 head.next나 head에 온다면, 마지막 노드의 head가 반환된다.

 

그래서, 우리는 마지막 전의 노드의 reverseList(head), (head = 마지막 전 노드)를 보게 된다. 여기서 이제 마지막 노드의 포인터를 마지막 전 노드로 바꿔주고 (head.next.next = head), 그리고, head.next = None, 마지막 전 노드의 포인터를 없애준다 (이는 처음 노드가 마지막 노드로 바뀔 때 end로 만들기 위한 base case인 듯?).

 

그렇게 return node를 해주는데, node는 영원히 마지막 노드의 포인터로 바뀌지 않으며, 그저 마지막 전 노드들의 포인터만 계속 호출된 function을 다시 돌아가며 바뀌게 된다.

 

<총평>

분명 easy인데 왜 이렇게 어려운 것일까.

 

Happy coding!

Reverse Linked List - LeetCode