Python Algorithm Q15

Q15 Reverse Linked List

---

Q

Given the head of a singly linked list, reverse the list, and return the reversed list.

Sample Input

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input: head = [1,2]
Output: [2,1]

Input: head = []
Output: []

Constraints

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

1. My Own Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node = head #the list to reverse
        rev = None # the space that reversed list is saved
        while node:
            rev, rev.next, node = node, rev, node.next
        return rev

#to test, you have to make to linked-list manually. 
inp = [1, 3, 5, 9]

list4 = ListNode(inp[3], None)
list3 = ListNode(inp[2], list4)
list2 = ListNode(inp[1], list3)
list1 = ListNode(inp[0], list2)

#for test
a = Solution()
new_head = a.reverseList(list1)

while new_head:
    print(new_head.val)

Trained with the crazy #13 problem, this question is too easy to me. But for the further time, I’ll write description for this solution. I fully utilizied multi-assignment in python, to prevent unnecessary use of memory.

1. Assign “head” to “node”. Then make empty list(=None) named rev.
2. Multi-Assign variables. Assign current node to the rev. Then by rev.next = rev, rev points the previous rev. Lastly, node moves to the next node.

** 2번에 대한 보충 설명 : 반복해서 언급하지만, multi-assignment는 그 연산 과정의 특징에 의해 여러 줄로 나눠서 할당했을 때와 다른 결과를 보인다.

A = node
B = rev
C = node.next
rev = A
rev.next = B
node = C

이런 식으로 계산되기 때문에 A, B를 계산할 때 예상이랑 다른 과정을 거치게 된다. rev에 먼저 node를 그대로 할당한다. 다음 “현재” 노드, 즉 방금 node를 막 할당한 그 rev가 가르키는 다음 주소 rev.next에 이전 rev를 넣는다. 따라서 rev는 할당하기 이전의 rev를 가르키게 된다.

2. Given Solution #1

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, rev = head, None
        while node:
            next, node.next = node.next, rev
            rev, node = node, next
        return rev

[Using Iteration]
Perfectly same as my solution, but the variable “next” is additionally used.

3. Given Solution #2

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(node: ListNode, prev: ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        return reverse(head)

[Using Recursion]
Not that hard. Just as complicated as the recursion problem usually does. Let’s explain it shortly.

1. Loop ends when node is None. All other cases infinitely loops. You can describe the code simply like this.

def reverse(~):

def reverseList( ):
    return reverse(head)

1. until node reaches None, it keeps assigning next, node.next = node.next, prev. “Next” is the following node of the current node. And by the code node.next = prev, the current node points the previous node. Then, repeat it by assigning next to the node, node to the prev.

** 2번에 대한 보충 설명 : 이 코드를 따라 그림을 그리다 보면 이 코드는 node를 하나씩 뒤로 밀고, 현재 노드가 가르키는 화살표의 방향을 정 반대로 돌리는 코드이다. 2번이 설명하는 것을 풀어서 설명하면, node가 none이 되어 재귀가 끝나기 전까지 계속 반복해서 다중 할당을 진행한다. next라는 변수가 현재 노드의 다음 노드를 가르키게 한다. 그 후, 현재 노드의 다음 주소를 prev으로 바꿔서 node가 이전 방향을 가르키게 한다.

Python MEMO의 linked_list 포스팅에 있는 gif를 참고하면 좀 더 쉽게 구조가 이해가 될 것이다.

마지막에 가서는 prev는 원래 연결 리스트의 맨끝을 가르키게 되는데, prev는 원래 연결 리스트의 역방향 연결 리스트이므로 거꾸로 head를 가르키게 된다. 따라서 point를 사전에 지정해놓거나 할 필요 없이 prev를 return하면 head_node를 구할 수 있다.

Overall Review

Pretty Easy. I merely felt some achievement after solving and understanding this question.