Reverse a linked list
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 206. Reverse Linked List — Given the head of a singly linked list, reverse the list and return the reversed list.
https://leetcode.com/problems/reverse-linked-list/description/
Quick Answer: This question evaluates understanding of linked list data structures and proficiency manipulating pointers or references to perform in-place transformations when reversing a linked list. Commonly asked in Coding & Algorithms interviews, it gauges algorithmic thinking and practical application-level competency in list operations rather than purely conceptual theory.
Given the head of a singly linked list, reverse the list in-place and return the new head. Each node has fields: val (int) and next (reference to the next node or None). Do not allocate new nodes or modify node values; only change next pointers. For examples and tests, the linked list is represented as an array of values; the function receives a linked list head and must return the head of the reversed list.
Constraints
- 0 <= n <= 100000 where n is the number of nodes
- -10^9 <= Node.val <= 10^9
- Must run in O(n) time
- Use O(1) extra space
- head may be None (empty list)
Solution
def reverse_list(head):
prev = None
curr = head
while curr is not None:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
Explanation
Iterate through the list while keeping a pointer to the previous node. For each node, store curr.next, redirect curr.next to prev, then move prev and curr forward. This reverses all next pointers in-place and returns the last processed node (prev) as the new head.
Time complexity: O(n). Space complexity: O(1).
Hints
- Maintain three pointers: prev, curr, next.
- Iteratively set curr.next = prev, then advance all pointers.
- A recursive solution is possible: reverse the rest, then set head.next.next = head and head.next = None.