šŸ”— LeetCode

Reverse Linked List

Easytwo pointersAmazonMicrosoftApple

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

Examples

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

Constraints

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

šŸ’” Hints

Hint 1

Can you reverse the links while iterating?

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear
Algorithmic Approach

Iterate through the list, changing the next pointer to point to the previous node.

Time ComplexityO(N)
Why:

Iterates through the linked list of N nodes once, reversing each node's next pointer in O(1) time.

Space ComplexityO(1)
Why:

Only three pointer variables (prev, curr, nxt) are modified in-place without allocating new nodes.

Big-O Growth CurveLinear (O(N))
Execution time scales directly in proportion to the input size.

šŸ” Dry Run

Solutionā± O(N) | šŸ’¾ O(1)
currā†“
head
1
2
3
4
5
Line2
prev=nullListNode
curr=headListNode

Initialize prev to null and curr to head.