Problems/Linked Lists/Linked List Reversal
Linked Lists
easy

Linked List Reversal

Reversing a linked list is a classic interview question that tests your understanding of pointer manipulation and data structure fundamentals. Mastering this problem demonstrates your ability to think algorithmically and handle complex data structures efficiently.

linked-listreversalpointersin-placeiteration

Problem Statement

Given the head of a singly linked list, reverse the order of the nodes in the list. The reversal must be done in-place. Return the new head of the reversed linked list.

Example 1
Input: 1 -> 5 -> 3 -> 8 -> NULL
Output: 8 -> 3 -> 5 -> 1 -> NULL
The original list is reversed such that the last element becomes the first, and so on.
Example 2
Input: 9 -> NULL
Output: 9 -> NULL
A single-element list remains unchanged after reversal.
Constraints
  • -The number of nodes in the list is in the range [0, 5000].
  • -Each node's value is in the range [-5000, 5000].
  • -The solution must use O(1) extra space.
  • -The solution must be implemented in-place.

Brute Force Approach

A brute-force approach would be like taking a train of toy cars, detaching each car, and then reassembling them in reverse order on a separate track. This involves creating a new linked list or using an array to store the values, which takes extra space. The time complexity is O(n) because you have to iterate through all elements, and the space complexity is O(n) because you're storing all node values.

TimeO(n)
SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem