Skip to main content

11. Reverse Linked List

easyAsked at Baidu

Reverse a singly linked list in-place and return the new head.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a singly linked list, reverse the list and return the reversed list's head. Solve it in O(n) time and O(1) extra space.

Constraints

  • Number of nodes is in [0, 5000]
  • -5000 <= Node.val <= 5000

Examples

Example 1

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

Example 2

Input
head = [1,2]
Output
[2,1]

Approaches

1. Stack copy

Push all nodes onto a stack, pop and re-thread next pointers.

Time
O(n)
Space
O(n)
const s=[];let n=head;while(n){s.push(n);n=n.next;}
const nh=s.pop()||null;let c=nh;while(s.length){c.next=s.pop();c=c.next;}if(c)c.next=null;return nh;

Tradeoff:

2. Iterative pointer flip

Maintain prev/curr; on each step capture curr.next, point curr at prev, slide both forward.

Time
O(n)
Space
O(1)
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Tradeoff:

Baidu-specific tips

Baidu reverses posting lists in their inverted index during merge passes, so the bar is the in-place 4-pointer dance — bringing recursion will trigger a follow-up about stack-overflow on long postings lists.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Reverse Linked List and other Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →