Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Reverse a Singly Linked List

Explore methods to reverse a singly linked list by implementing iterative and recursive approaches. Understand how to manipulate pointers to change node order, and evaluate solutions by their time and space complexity for effective problem-solving.

We'll cover the following...

Statement

Given the head of a singly linked list, reverse the linked list and return its new or updated head.

Example

Consider the following linked list:

G rootptr head 7 7 rootptr->7 14 14 7->14 21 21 14->21 28 28 21->28 NULL NULL 28->NULL

Return the pointer to the reversed linked list as shown in the figure:

G rootptr head 28 28 rootptr->28 21 21 28->21 14 14 21->14 7 7 14->7 NULL NULL 7->NULL

Sample input

[7, 14, 21, 28]

Expected output

[28, 21, 14, 7]

Try it yourself #

#include "LinkedList.cpp"
using namespace std;
LinkedListNode* Reverse(LinkedListNode* head) {
	//TODO: Write - Your - Code
}

Solution 1

If the linked list only contains 0 or 1 node, then the current list can be returned as it is. If there are two or more nodes, then the iterative solution starts with two node pointers:

  • First pointer: points to the head of the input linked list.
  • Second pointer: It points to the head’s next node.

We then set the next of the first pointer to NULL. It becomes the last node in the new reversed linked list. The first pointer always points to the ...