Last Updated on April 12, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
In this problem, we will be given a linked list and are required to print the reverse of the linked list without using conventional methods.
Problem Statement Understanding
This is an interesting problem. According to the problem statement, we will have to print the reverse of the given linked list without using any conventional method for reversing the linked list.
If the given linked list: 23 → 12 → 2 → 10
- Then the reverse of the linked list is: 10 → 2 → 12 → 23.
- Our output will be the print of the reverse of the linked list, which will be 10, 2, 12, 23.
If the given linked list is: 1 → 3 → 5 → 7 → 9 → 11 → 13 → 15
- In this case, our output will be 15, 13, 11, 9, 7, 5, 3, 1.
Some more examples
Sample Input 1: 1 → 2 → 3 → 4
Sample Output 1: 4, 3, 2, 1
Sample Input 2: 2 → 4 → 6 → 8 → 10
Sample Output 2: 10, 8, 6, 4, 2
Explanation: We are printing the reverse of the given linked list.
Well, reversing a linked list is pretty easy, right? But here, we can’t reverse the linked list. So, how should we approach the problem?
- The answer is Carriage return ("r"). Whenever we use "r", it commands the printer to move the position of the cursor to the first position on the same line.
Let us have a glance at the approach.
Approach
The approach is going to be pretty straightforward.
- First, we will find out the length of the linked list.
- Then, we will print (n-1) blank spaces and then print the 1st element then the carriage return "r", further again we will print (n-2) blank spaces and the 2nd element and then again carriage return "r" and so on… until we reach the end of the list.
Note: What we are doing above is, after printing (n-1) blank spaces and then the element, we are commanding the cursor to jump to the start of the line. So that, when the next printing portion happens, the (n-2) spaces are given from the start of the line and then the next element is printed and hence in this way the printing will happen in a reverse fashion.
Algorithm
- Find the length of the given linked list, and store it in n.
- Initialize a variable j with 0.
- Now initialize a pointer curr with head and start traversing the list using curr.
- While traversing the list:
- Run a for loop to print the proper number of blank spaces before printing the current node’s data. Actually, print (n-j) spaces, because that is the proper spacing which will give the perfect look of reverse printing.
- After printing the blank spaces, print the current’s nodes data and use carriage return (printf(“%d\r”, curr→data)).
- Increment the current node by curr = curr→next.
- Increment j by 1.
- This way, our list will get printed in reverse order.
Dry Run
Code Implementation
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to reverse the linked list */
static void reverse(struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next = NULL;
while (current != NULL) {
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed Linked list \n");
printList(head);
getchar();
}
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int val;
struct node* next;
} node;
node* head = NULL;
// Function to return the No of nodes present in the linked list
int count(node* head)
{
node* p = head;
int k = 1;
while (p != NULL) {
p = p->next;
k++;
}
return k;
}
node* ll_reverse(node* head) // to reverse the linked list
{
node* p = head;
long int i = count(head), j = 1;
long int arr[i];
while (i && p != NULL) {
arr[j++] = p->val;
p = p->next;
i--;
}
j--;
while (j) // loop will break as soon as j=0
cout << arr[j--] << " ";
return head;
}
// Function to insert node at the end of linked list
node* insert_end(node* head, int data)
{
node *q = head, *p = (node*)malloc(sizeof(node));
p->val = data;
while (q->next != NULL)
q = q->next;
q->next = p;
p->next = NULL;
return head;
}
node* create_ll(node* head, int data) // create ll
{
node* p = (node*)malloc(sizeof(node));
p->val = data;
if (head == NULL) {
head = p;
p->next = NULL;
return head;
}
else {
head = insert_end(head, data);
return head;
}
}
// Driver code
int main()
{
int i = 5, j = 1;
while (i--)
head = create_ll(head, j++);
head = ll_reverse(head);
return 0;
}
import java.io.*;
import java.util.*;
/* Structure of a linked list node */
class Node {
int data;
Node next;
Node(int val)
{
data = val;
next = null;
}
}
public class PrepBytes
{
/* Using this function we will be printing the reverse of the given linked list */
static void printReverse(Node head, int n)
{
int j = 0;
Node curr = head;
while (curr != null) {
for (int i = 0; i < (n-j); i++)
System.out.print(" ");
System.out.print(curr.data +"\r" );
curr = curr.next;
j++;
}
}
/* Using this function we will be adding a new node to the head of the given linked list */
static Node push(Node head, int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
return head;
}
/* Using this function we will be printing the elements of the given linked list */
static int printList(Node head)
{
int i = 0;
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
i++;
}
return i;
}
public static void main(String args[])
{
Node head = null;
head = push(head, 10);
head = push(head, 2);
head = push(head, 12);
head = push(head, 23);
System.out.println("Printing original given linked list: ");
int n = printList(head);
System.out.println();
System.out.println("Printing reversed linked list: ");
printReverse(head, n);
System.out.println();
}
}
# Structure of a linked list node
class Node:
def __init__(self):
self.data= 0
self.next=None
# Using this function we will be printing the reverse of the given linked list
def printReverse( head_ref, n):
j = 0
current = head_ref
while (current != None):
i = 0
while ( i < (n - j) ):
print(end=" ")
i = i + 1
print( current.data, end = "\r")
current = current.next
j = j + 1
# Using this function we will be adding a new node to the head of the given linked list
def push( head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
# Using this function we will be printing the elements of the given linked list
def printList( head):
i = 0
temp = head
while (temp != None):
print( temp.data,end = " ")
temp = temp.next
i = i + 1
return i
head = None
head = push(head, 10)
head = push(head, 2)
head = push(head, 12)
head = push(head, 23)
print("Printing original given linked list:")
n = printList(head)
print("\nPrinting reversed linked list: ")
printReverse(head, n)
print()
Output
Printing original given linked list:
23 12 2 10
Printing reversed Linked list:
10 2 12 23
Time Complexity: O(n), as list traversal is needed
[forminator_quiz id=”5056″]
So, in this article, we have tried to explain an interesting method to print the reverse of a linked list. The unique constraints of this problem are what makes this problem an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.