Saturday, 18 July 2015

How to reverse Single linklist in java

Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list.It has below properties:

  1. Elements can be inserted indefinitely.
  2. They don’t take contiguous memory locations. For this reason, they are suitable to be used even if the disk or memory is fragmented.
  3. You can traversal in one direction

We can reverse the linkedlist using 2 approach:

1. Iterative approach:

public LinkedList<Integer> reverse(LinkedList<Integer> header) {
        if (header == null) {
            return null;
        LinkedList<Integer> prev = null;
        LinkedList<Integer> next = header;
        while (header != null) {
            next = header.getNext();
            prev = header;
            header = next;
        return prev;

2. Recursive approach: 

 private LinkedList<Integer> reverseRecursiveWay(LinkedList<Integer> header) {
        if (header == null) {
            return null;
        LinkedList<Integer> startNode = reverseRecursiveWay(header.getNext());
        if (startNode != null) {
            LinkedList<Integer> next = header.getNext();
            /* Below statement is required because when all the nodes
              are reverse,  reached to first node and
               want to make sure that initial header will not
              point to second element.*/
            return startNode;
        return header;

LinkedList class looks like: 

public class LinkedList<T> {
    public LinkedList() {


    public LinkedList(T data) { = data;

    private T data;
    private LinkedList<T> next;

    public T getData() {
        return data;

    public void setData(T data) { = data;

    public LinkList<T> getNext() {
        return next;

    public void setNext(LinkedList<T> next) { = next;


No comments:

Post a Comment