[Leetcode] 206. Reverse Linked List

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

initial

as always i had trouble with linked list bcos it is so hard to debug but with chatgpt i finally kinda undestand

lets firsst look at how linked list is built with listNode

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

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

# Function to print the linked list
def printLinkedList(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

# Print the original linked list
print("Original Linked List:")
printLinkedList(head)

# Create a Solution instance and reverse the linked list
solution = Solution()
reversed_head = solution.reverseList(head)

# Print the reversed linked list
print("\nReversed Linked List:")
printLinkedList(reversed_head)

so head is making a linked list. I plaed a debug point on that to see how it is built and the building starts from the end of ListNode(5). So listnode 5 has value 0 and next None. Then we go to ListNode(4, ListNode(5)). Now here, value is 4 and next is pointint to ListNode(5). So we have something liek 4 ->5. Then we go ListNode(3, ListNode(4, ListNode(5))). value is 3 and next is ListNode(4, ListNode(5)) so like 3->4->5.

So we are building linked list from the end to start.

So how do we reverse this linked list?

We can make a linked list just like how we built this head linked list. We first set prev = None, which will act as the previous listNode. While head, we assign a pointer called cur that points to head (linkedlist) and shift our head to head.next. cur.next will point to prev so effectively at first iteration, cur is (5,none). Then prev will be reassigned as this cur (5,none) cuz next iterations will build upon this value like 4,(5,none).

complexity

i thought space is n but its actually 1 cuz of pointers

The time complexity of the provided reverseList method is O(n), where n is the number of nodes in the linked list. This is because the method iterates through each node in the list once, and each iteration involves constant-time operations.

The space complexity is O(1), meaning the algorithm uses a constant amount of extra space, regardless of the size of the input linked list. The only additional memory used is for the prev, cur, and head variables, which are not dependent on the size of the input. The algorithm does not use any data structures that grow with the input size.

So, to summarize:

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