Reverse a Linked List

Problem : 

You are given a Singly Linked List. You have to write a program to reverse a linked list and then print the reversed linked list.

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.

Your Task:

The task is to complete the function reverseList() with head reference as the only argument and should return a new head after reversing the list.

Expected Time Complexity: O(N).

Expected Auxiliary Space: O(1).

Solutions

Java Code:

//Initial Template for Java

import java.util.*;
import java.io.*;

class Node
{
    int data;
    Node next;
    Node(int d)
    {
        data = d;
        next = null;
    }
}

public class CB
{
    Node head;  // head of lisl
    Node lastNode;
    static PrintWriter out;
    /* Linked list Node*/


    /* Utility functions */

    /* Inserts a new Node at front of the list. */
    public void addToTheLast(Node node)
    {

        if (head == null)
        {
            head = node;
            lastNode = node;
        }
        else
        {
            Node temp = head;
            lastNode.next = node;
            lastNode = node;
        }
    }
    /* Function to print linked list */
    void printList()
    {
        Node temp = head;
        while (temp != null)
        {
            out.print(temp.data+" ");
            temp = temp.next;
        }
        out.println();
    }



    
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int t= Integer.parseInt(br.readLine());

        while(t>0)
        {
            int n = Integer.parseInt(br.readLine());

            CB cb = new CB();
                        String nums[] = br.readLine().split(" ");
            if (n > 0)
            {
                int a1= Integer.parseInt(nums[0]);
                Node head= new Node(a1);
                cb.addToTheLast(head);
            }
            for (int i = 1; i < n; i++)
            {
                int a = Integer.parseInt(nums[i]);
                cb.addToTheLast(new Node(a));
            }


            cb.head = new ReverseLL().reverseList(cb.head);
            
            cb.printList();
            
            t--;
        }
        out.close();
    }
}

// } Driver Code Ends
//function Template for Java

/* Return reference of new head of the reverse linked list 
 class Node {
     int value;
    Node next;
    Node(int value) {
        this.value = value;
    }
} */

class ReverseLL
{
    // This function should reverse linked list and return
   // head of the modified linked list.
   Node reverseList(Node head)
   {
        // add code here
       if(head==null||head.next==null)
       {
           return head;
       }
       else {
           Node rev = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return rev;
       }
      
   }
}

C++ Code:

//Initial Template for C++

// C program to find n'th Node in linked list
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;

/* Link list Node */
struct Node {
    int data;
    struct Node *next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};



 // } Driver Code Ends
/* Linked List Node structure:

struct Node
{
    int data;
    struct Node *next;
}

*/

class Solution
{
    public:
    struct Node* reverseList(struct Node *head)
    {
       if(head==NULL||head->next==NULL)
       {
           return head;
       }
       else {
           Node *rev = reverseList(head->next);
           head->next->next = head;
           head->next = NULL;
           return rev;
       }
    }
    
};
    


// { Driver Code Starts.

void printList(struct Node *head)
{
    struct Node *temp = head;
    while (temp != NULL)
    {
       printf("%d ", temp->data);
       temp  = temp->next;
    }
}

/* Driver program to test above function*/
int main()
{
    int T,n,l,firstdata;
    cin>>T;

    while(T--)
    {
        struct Node *head = NULL,  *tail = NULL;

        cin>>n;
        
        cin>>firstdata;
        head = new Node(firstdata);
        tail = head;
        
        for (int i=1; i<n; i++)
        {
            cin>>l;
            tail->next = new Node(l);
            tail = tail->next;
        }
        
        Solution ob;
        head = ob. reverseList(head);
        
        printList(head);
        cout << endl;
    }
    return 0;
}

  // } Driver Code Ends