FastPrepReverse a Singly Linked List

Reverse a Singly Linked List

Google logoGoogle● EasyINTERNONSITE INTERVIEW
Learn

Problem statement

You are given the head head of a finite singly linked list of contacts. Reverse every next pointer in place and return the new head.

The returned list must contain exactly the original nodes and values in reverse order. Node values may repeat. If head is null, return null; if the list contains one node, return that same node.

Interview extensions

  • Explain how to reverse the complete list recursively.
  • Explain how to reverse only a contiguous segment from the m-th node through the n-th node.

Function

reverseList(head: ListNode) → ListNode

Examples

Example 1

head = [1,2,3,4,5]return = [5,4,3,2,1]

Every pointer is reversed, so the original tail becomes the new head.

Example 2

head = []return = []

An empty list has no nodes to reverse, so the result is null.

Example 3

head = [7]return = [7]

A one-node list is already reversed, so the same node is returned.

Example 4

head = [1,1,2]return = [2,1,1]

Repeated values are preserved because the nodes, rather than a set of values, are reversed.

Constraints

  • 0 <= number of nodes <= 100000
  • -10^9 <= node.val <= 10^9
  • The input list is finite and acyclic.
  • Each node has only a next pointer; there is no prev pointer.

More Google problems

See Google hiring insights
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode next;
 * }
 */
public ListNode reverseList(ListNode head) {
  // Write your code here.
}
head[1,2,3,4,5]
expected[5,4,3,2,1]
Checking account…