REVERSE A LINKED LIST

Concepts Used

Linked list,recursion.

Difficulty Level

Easy.

Problem Statement :

Given pointer to the head node of a linked list, the task is to reverse the linked list.

See original problem statement here

Example:

Assume that we have linked list 1 → 2 → 3 → Ø, 
we have to change it to Ø ← 1 ← 2 ← 3.

Explanation:

Approach 1(Iterative approach):

While you are traversing the list, change the current node’s next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

struct Node* Reverse(Node *head)
    {
    Node *tail, *t;
    tail = NULL;
    while (head != NULL)
     {
        t = head->next;
        head->next = tail;
        tail = head;
        head = t;
    }
    return tail;
     // Complete this method
       }
 public static Node reverseLinkedList(Node currentNode)
      {
        // For first node, previousNode will be null
        Node previousNode=null;
        Node nextNode;
        while(currentNode!=null)
        {
            nextNode=currentNode.next;
            // reversing the link
            currentNode.next=previousNode;
            // moving currentNode and previousNode by 1 node
            previousNode=currentNode;
            currentNode=nextNode;
        }
        return previousNode;
      }
def Reverse(head):
    
    tail = NULL
    while (head != NULL):
    
        t = head.next
        head.next = tail
        tail = head
        head = t
    
    return tail

Approach 2(Using recursion):

We can find it easier to start from the bottom up,by asking and answering tiny questions:

  1. What is the reverse of NULL? NULL.

  2. What is the reverse of a one element list?The element itself.

  3. What is the reverse of an n element list? The reverse of the second element followed by the first element.

Refer to commented implementation

     Node Reverse(Node head) {

       /* We have two conditions in this if statement.
       This first condition immediately returns null
       when the list is null. The second condition returns
        the final node in the list. That final node is sent
        into the "remaining" Node below.
        -----------------------------------------------------*/

       if (head == null || head.next == null) {  
             return head;  
         }

     /* When the recursion creates the stack for A -> B -> C
       (RevA(RevB(RevC()))) it will stop at the last node and
        the recursion will end, beginning the unraveling of the
        nested functions from the inside, out. 
       -----------------------------------------------------*/

        Node remaining = Reverse(head.next);

     /* Now we have the "remaining" node returned and accessible
      to the node prior. This remaining node will be returned
      by each function as the recursive stack unravels.

      Assigning head to head.next.next where A is the head
      and B is after A, (A -> B), would set B's pointer to A,
      reversing their direction to be A <- B.
      -----------------------------------------------------*/

      head.next.next = head; 

      /* Now that those two elements are reversed, we need to set
      the pointer of the new tail-node to null.
      -----------------------------------------------------*/

      head.next = null;  

      /* Now we return remaining so that remaining is always
      reassigned to itself and is eventually returned by the
      first function call.
      -----------------------------------------------------*/

      return remaining; 
      }

SOLUTION:

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/* Reverses a Linked List using recursion */
void reverse(struct node* nodePtr) {
      
    /* empty list */
    if (nodePtr == NULL)
       return;   
    /* Last node (tail node)*/
    if(nodePtr->next == NULL){
        head = nodePtr;
        return;   
    }
 
    /* reverse the rest of list and put the first element at the end */
    reverse(nodePtr->next);
    nodePtr->next->next = nodePtr;  
    nodePtr->next = NULL;               
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(1);  
    insert(2); 
    insert(3); 
    insert(4);
    insert(5);
    
    printf("\nLinked List\n");
    printLinkedList(head);
    
    /* Reverse Linked List */
    reverse(head);
    printf("\nReversed Linked List\n");
    printLinkedList(head);
    
    return 0;
}
 #include <bits stdc++.h="">
     using namespace std;
    struct node{
    int data;
    node* next;
    };
     node* newnode(int x)
    {
    node* temp=new node();
    temp->data=x;
    temp->next=NULL;
    return temp;
    }
    node* reverse(node* head)
    {
     if(head==NULL||head->next==NULL)return head;
    node* restlist=reverse(head->next);
    head->next->next=head;
    head->next=NULL;
     return restlist;
    }
    int main()
    {
    //write your code here
    int t;cin>>t;
    while(t--)
    {
    int n;
    cin>>n;
    int x;cin>>x;
    node* temp=newnode(x);
    node* head=temp;
    for(int i=1;i<n;i++) {="" int="" x;cin="">>x;
      head->next=newnode(x);
      head=head->next;
    }
    node* head1=reverse(temp);
    while(head1!=NULL)
    {
      cout<<head1->data<<" ";
      head1=head1->next;
    }
    cout<<"\n";
     }
     return 0;
     }
import java.io.*;
     import java.util.*;
    public class Main{
    static class SinglyLinkedListNode {
        public int data;
        public SinglyLinkedListNode next;
        public SinglyLinkedListNode(int nodeData) {
            this.data = nodeData;
            this.next = null;
        }
    }
    static class SinglyLinkedList {
        public SinglyLinkedListNode head;
        public SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            this.head = null;
            this.tail = null;
        }

        public void insertNode(int nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }

            this.tail = node;
        }
    }
    static void printLinkedList(SinglyLinkedListNode head)
    {
        SinglyLinkedListNode temp=head;
        while(temp!=null)
        {
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
        System.out.println();
    }
    static SinglyLinkedListNode reverseLinkedList(SinglyLinkedListNode head) {
        SinglyLinkedListNode prev = null;
        SinglyLinkedListNode current = head;
        SinglyLinkedListNode next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        return head;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        int testCases = scanner.nextInt();

        while (testCases-- > 0) {
            SinglyLinkedList llist = new SinglyLinkedList();

            int llistCount = scanner.nextInt();

            for (int i = 0; i < llistCount; i++) {
                int llistItem = scanner.nextInt();

                llist.insertNode(llistItem);
            }

            printLinkedList(reverseLinkedList(llist.head));

        }

        scanner.close();
    }
    }
class node:
	def __init__(self):
		self.data = None
		self.next = None

def newnode(x):
    
    temp= node()
    temp.data = x
    temp.next = None
    return temp
    

def reverse(head):
    
    if(head == None or head.next == None):
    	return head
    
    restlist = reverse(head.next)
    head.next.next = head
    head.next = None
    return restlist

for _ in range(int(input())):

	n = int(input())
	a = list(map(int,input().split()))
	temp = newnode(a[0])
	head = temp

	for i in range(1, n):
		head.next = newnode(a[i])
		head = head.next

	head1 = reverse(temp)

	while head1:
		print(head1.data, end = " ")
		head1 = head1.next
	print()


[forminator_quiz id="1506"]

This article tried to discuss the concept of Linked List, Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Linked List, Recursion you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *