Data Structures and Algorithms — Linked Lists #3 - Reverse a Linked List

A step-by-step guide to cracking popular Linked List interview questions

Problem Statement:

Given a linked list of N nodes. The task is to reverse this list.

Example 1:

Input:
LinkedList: 1->2->3->4->5->6
Output: 6 5 4 3 2 1
Explanation: After reversing the list, 
elements are 6->5->4->3->2->1.

Example 2:

Input:
LinkedList: 2->7->8->9->10
Output: 10 9 8 7 2
Explanation: After reversing the list,
elements are 10->9->8->7->2.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Asked in following companies

Accolite,Adobe, Amazon, Cisco, D-E-Shaw, Goldman Sachs, Microsoft ,Paytm

Concept:

The main idea behind reversing the linked list is that the current tail in the linked list becomes the new head node and the current head becomes the new tail node. All the other connections in the list are reversed.

Step-by-step Approach:

1. Initialize the three nodes/pointers:

prev points to null

current points to the current head

next points to null

2. Traverse the linked list, until the current node is not equal to null.

3. Once the ‘next’ pointer reaches a null node, it means that we have reached the tail node. When the last iteration of the loop is carried out, the tail becomes the new head.

4. After the execution of the loop, the current and next point to null, and prev points to the new head of the reversed list. Hence, we return the ‘prev’ pointer.

Code:

Complexity Analysis:

Time complexity: O(n)

Here, ’n’ denotes the number of nodes in the linked list.

Space complexity: O(1).

If you liked this article, please click the “clap” button 👏 a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow me Varsha Das to receive my weekly articles.

Connect with me — Varsha Das | LinkedIn

Follow my Youtube channel where we discuss Data Structures & Algorithms.

Thanks for reading.

Happy learning! 😁