Reverse Linked List

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

考え方としては、

1 → 2 → 3 → 4 → 5

1 ← 2 ← 3 ← 4 ← 5

とするように考える。

回答方法は iterative なやり方と recursive なやり方がある。 iterative なやり方は 2つの pointer を使う。

prev と curr

まず prev に　None を設定する。 curr は head にする

Null → 1 → 2 → 3 → 4 → 5 　↑ ↑ prev curr

ループしている間 Linked List の 矢印の向き (curr.next) をずらしつつ、prev と next の pointer もずらしていく。

Null ← 1 → 2 → 3 → 4 → 5 → Null ↑ ↑ prev curr

Null ← 1 ← 2 → 3 → 4 → 5 → Null ↑ ↑ prev curr

Null ← 1 ← 2 ← 3 → 4 → 5 → Null ↑ ↑ prev curr

Null ← 1 ← 2 ← 3 ← 4 → 5 → Null ↑ ↑ prev curr

Null ← 1 ← 2 ← 3 ← 4 ← 5 → Null ↑ ↑ prev curr

curr が Null になりループを抜けるので、 最後に head を prev に設定する。

Time complexity: O(n) Mem complexity: O(1)

# 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):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None
        curr = head

        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

recursive

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

head: ListNode{val: 4, next: ListNode{val: 5, next: None}} reversedListHead: ListNode{val: 5, next: None}

head: ListNode{val: 4, next: None} reversedListHead: ListNode{val: 5, next: ListNode{val: 4, next: None}}

head: ListNode{val: 3, next: ListNode{val: 4, next: None}} reversedListHead: ListNode{val: 5, next: ListNode{val: 4, next: None}}

head: ListNode{val: 3, next: None} reversedListHead: ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: None}}}

head: ListNode{val: 2, next: ListNode{val: 3, next: None}} reversedListHead: ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: None}}}

head: ListNode{val: 2, next: None} reversedListHead: ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: None}}}}

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

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

Time complexity: O(n) Mem complexity: O(n)