7. Reverse Linked List

1 Stack

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        found_values = []  #stack
        node_in_original = head

        while node_in_original:
            found_values.append(node_in_original.val)
            node_in_original = node_in_original.next
        
        dummy = ListNode()
        node_in_reversed = dummy

        while found_values:
            node_in_reversed.next = ListNode(found_values.pop())
            node_in_reversed = node_in_reversed.next
        
        return dummy.next

スタック積み込んで、一個ずつ出す。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current_node = head
        previous_node = None

        while current_node:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
        
        return previous_node

ポインター2個使って繋ぎ変えていく。空間計算量が定数。ぶっちゃけあまり思いつかないなぁ。