Coderust: Hacking the Coding Interview/

...

/

Reverse a Singly Linked List

Reverse a Singly Linked List

Reverse the singly linked list and return the head of the reversed linked list.

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 #

main.cpp
LinkedList.cpp
LinkedListNode.cpp
#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 ...