Question

Reverse nodes in linked list java

Answer 1

See the following running example to reverse the linked list:-

package com.ds.linkedlist;

public class Node<T> {

    private T data;
    private Node<T> next;
   
    public Node(){
        setData(null);
        setNext(null);
    }
   
    public Node(T data){
        setData(data);
        setNext(null);
    }
   
    public T getData(){
        return data;
    }
   
    public void setData(T data){
        this.data = data;
    }
   
    public Node<T> getNext(){
        return next;
    }
   
    public void setNext(Node<T> next){
        this.next = next;
    }
   
}

package com.ds.linkedlist;

import java.util.HashMap;

public class SingleLinkedList<T> {
    Node<T> head = null;
    public Node<T> reverse() {
        if (head != null) {
            Node<T> prev = null;
            while (head.getNext() != null) {
            Node<T> next = head.getNext();
            head.setNext(prev);
            prev = head;
            head = next;
            }
            head.setNext(prev);
        }
        return head;
        }
    //Without temp variable
    public Node reverse2(){
        Node currNode = head;
        if(currNode == null){
            return null;
        }
        while(currNode != null){
            Node newNode = new Node(currNode.getData());
            if(reverseHead == null){
                reverseHead = newNode;
            }else{
                newNode.setNext(reverseHead);
                reverseHead = newNode;
            }
            currNode = currNode.getNext();
        }
        head = reverseHead;
        return head;
    }
    public void addFirst(T data){
        if(data == null){
            return;
        }
        if(head == null){
            head = new Node<T>(data);
        }else{
            Node<T> newNode = new Node<T>(data);
            newNode.setNext(head);
            head = newNode;
        }
    }
   
    public void getNodeData(){
        Node<T> tempNode = head;
        if(tempNode==null){
            return;
        }
        while(tempNode != null){
            System.out.print(tempNode.getData()+" ");
            tempNode = tempNode.getNext();
        }
    }
}

package com.ds.linkedlist;

public class LinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<Integer>();
        singleLinkedList.addFirst(10);
        singleLinkedList.addFirst(20);
        singleLinkedList.addFirst(30);
        singleLinkedList.addFirst(30);
        singleLinkedList.addFirst(40);
        System.out.println("Node List:-");
        singleLinkedList.getNodeData();
        singleLinkedList.reverse2();
        System.out.println("Reverse Linked List:");
        singleLinkedList.getNodeData();
    }
}

Output:-
Node List:-
40 30 30 20 10
Reverse Linked List:
10 20 30 30 40

Answer 2

See the following code to reverse linked list by using Time Complexity O(n) and Space Complexity O(n):-

/**

* Time Complexity O(n)

* Space Complexity O(n)

*/

public Node reverseLinkedList(Node head) {

Node reverseLinkedList = null;

LinkedList linkedList = new LinkedList();

while(head != null) {

reverseLinkedList = linkedList.insertBegin(head.data);

head = head.next;

}

return reverseLinkedList;

}

Output:-

Print LinkedList Data:- 

40 5 50 20 

After Reversing LinkedList:- 

20 50 5 40 

Answer 3

Following code for reversing linked list by using two reference variables and taking Time Complexity O(n) :-

/**

* Time Complexity O(n) 

*/

public Node reverseLinkedListUsingTwoReferences(Node head) {

Node prev = null;

Node current = head;

while(current != null) {

Node next = current.next;

current.next = prev;

prev = current;

current = next;

}

head = prev;

return head;

}

Output:-

Print LinkedList Data:- 

40 5 50 20

After Reversing LinkedList By Using Two refrences:- 

20 50 5 40 

Answer 4

Reverse linked list by recursion in java. See the following code:-

/**

* Time Complexity O(n)

*/

public Node reverseLinkedListUsingRecursion(Node current, Node prev) {

if(current == null) {

return prev;

}

Node next = current.next;

current.next = prev;

return reverseLinkedListUsingRecursion(next, current);

}

Output:-

Print LinkedList Data:-

40 5 50 20

After Reversing LinkedList By Using Recursion:-

20 50 5 40