How to reverse Singly Linked List?

1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer.
package com.java2novice.ds.linkedlist;
  
public class SinglyLinkedListImpl<T> {
  
    private Node<T> head;
      
    public void add(T element){
          
        Node<T> nd = new Node<T>();
        nd.setValue(element);
        System.out.println("Adding: "+element);
        Node<T> tmp = head;
        while(true){
            if(tmp == null){
                //since there is only one element, both head and 
                //tail points to the same object.
                head = nd;
                break;
            } else if(tmp.getNextRef() == null){
                tmp.setNextRef(nd);
                break;
            } else {
                tmp = tmp.getNextRef();
            }
        }
    }
      
    public void traverse(){
          
        Node<T> tmp = head;
        while(true){
            if(tmp == null){
                break;
            }
            System.out.print(tmp.getValue()+"\t");
            tmp = tmp.getNextRef();
        }
    }
     
    public void reverse(){
         
        System.out.println("\nreversing the linked list\n");
        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next = null;
        while(current != null){
            next = current.getNextRef();
            current.setNextRef(prev);
            prev = current;
            current = next;
        }
        head = prev;
    }
     
    public static void main(String a[]){
        SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();
        sl.add(3);
        sl.add(32);
        sl.add(54);
        sl.add(89);
        System.out.println();
        sl.traverse();
        System.out.println();
        sl.reverse();
        sl.traverse();
    }
}
  
class Node<T> implements Comparable<T> {
      
    private T value;
    private Node<T> nextRef;
      
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
    public Node<T> getNextRef() {
        return nextRef;
    }
    public void setNextRef(Node<T> ref) {
        this.nextRef = ref;
    }
    @Override
    public int compareTo(T arg) {
        if(arg == this.value){
            return 0;
        } else {
            return 1;
        }
    }
}

Output:
Adding: 3
Adding: 32
Adding: 54
Adding:
89 3 32 54 89
reversing the linked list
89 54 32 3

Share

Recent Posts

Find out duplicate number between 1 to N numbers.

[crayon-662d4edf614c0440379513/]

5 years ago

Find out middle index where sum of both ends are equal

You are given an array of numbers. Find out the array index or position where…

5 years ago

Write a singleton class in Java

Singleton class means you can create only one object for the given class. You can…

5 years ago

Write a java program to reverse a string?

1) Using StringBuffer class In this method, we use reverse() method of StringBuffer class to reverse the…

5 years ago

Write a java program to remove all white spaces from a string.?

1) Using replaceAll() Method. In the first method, we use replaceAll() method of String class…

5 years ago

Singly linked list implementation

Singly Linked Lists are a type of data structure. It is a type of list.…

5 years ago