LeetCode / Reversed Linked List

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

1つのLinked Listをsortして逆順にする問題。

解法1

Iterativeな解法。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

head, curr, prevの値の移り変わりは以下の通り。

head ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}
curr ListNode{val: 1, next: None}
prev ListNode{val: 1, next: None}

head ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}
curr ListNode{val: 2, next: ListNode{val: 1, next: None}}
prev ListNode{val: 2, next: ListNode{val: 1, next: None}}

head ListNode{val: 4, next: ListNode{val: 5, next: None}}
curr ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
prev ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}

head ListNode{val: 5, next: None}
curr ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}
prev ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}

head None
curr ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}}
prev ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}}

headの各要素を走査する間に、以下の操作が走ります。

curr = head
head = head.next # headを1つ先に進める
curr.next = prev # currの2つ目以降の要素に前のループで格納しておいたprevの値を入れる
prev = curr # prevにcurrの値を入れる(新たな要素が1つ先頭に加わる)

解法2

Recursiveな解法。

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