Tuesday, November 3, 2015

Reverse a Single Linked List in Java

Input: 
LinkedList ll = new LinkedList(0);
ll.append(1);
ll.appendList(2,3,4,5,6,7,8,9);
ll.insertFirst(-1);
ll.insertMiddle(33, 3);
ll.printList();
ll.ReverseList();
ll.printList();
ll.ReverseList();
ll.printList();

 

Program:

public class LinkedList {
    LinkedList next;
    int data;
    private int size;
    public static final int ERROR_CODE = -99999;
    public LinkedList(int data) {
        next = null;
        this.data = data;
        this.size=0;
    }
   
    public int sizeOfList()    {
        return ((this.size)+1);
    }
   
    public void appendList(int... data)    {
        int length = data.length;
        for(int i=0; i<length; i++)
            append(data[i]);
    }
   
    public void append(int data)    {
        LinkedList L = this;
        for(; L.next!=null; L=L.next)    {
        }
        L.next = new LinkedList(data);
        this.size++;
    }
   
    public void printList()    {
        LinkedList L = this;
        StringBuffer sb = new StringBuffer();
        for(; L.next!=null; L=L.next)    {
            sb.append(L.data);
            sb.append(", ");
        }
        sb.append(L.data);
        sb.append(", ");
        System.out.println(sb.toString());
    }
   
    public int removeLast()    {
        LinkedList L = this;
        for(;L.next.next!=null;L=L.next)    {}
        int pop = L.next.data;
        L.next=null;
        this.size--;
        return pop;
    }
   
    public void insertFirst(int data)    {
        LinkedList L = this;
        int headData = L.data;
        LinkedList temp = L.next;
        LinkedList newNode = new LinkedList(headData);
        newNode.next = temp;
        L.data = data;
        L.next = newNode;
        this.size++;
    }
   
    public void Rotate(int times)    {
        for(int i=0;i<times;i++)    {
            insertFirst(removeLast());
        }
        insertFirst(removeLast());
    }
   
    private int removeHead()    {
        LinkedList L = this;
        if(L.next==null)    {
            System.out.println("Single Element List can't be removed");
            return ERROR_CODE;
        }    else    {
            int val = L.data;
            LinkedList temp = L.next.next;
            L.data=L.next.data;
            L.next=temp;
            this.size--;
            return val;
        }
       
    }
   
    public void insertMiddle(int data, int possition)    {
        if(possition==1)    insertFirst(data);
        else if(possition==sizeOfList())    append(data);
        else    {
            LinkedList L = this;
            for(int i=2; i<possition; i++)
                L=L.next;
            LinkedList newNode = new LinkedList(data);
            LinkedList temp = L.next;
            L.next = newNode;
            L.next.next=temp;
            this.size++;
        }
    }
   
    public int remove(int possition)    {
        if(possition==1)    return removeHead();
        else if(possition<=this.size)    {
            LinkedList L = this;
            possition--;
            for(int i=1; i<possition; i++)
                L=L.next;
            int val = L.next.data;
            L.next=L.next.next;
            this.size--;
            return val;
        }    else if(possition==sizeOfList())    {
            return removeLast();
        }
        else    {
            System.out.println("Error, no possition found");
            return ERROR_CODE;
        }
    }
   
    public int Replace(int data, int possition)    {
        LinkedList L = this;
        if(possition>sizeOfList())    {
            return ERROR_CODE;
        }    else if(possition==1)    {
            int val = L.data;
            L.data=data;
            return val;
        }    else    {
            for(int i=2; i<possition; i++)   
                L=L.next;
            int val = L.next.data;
            L.next.data=data;
            return val;
        }
    }
   
    public int getValue(int possition)    {
        LinkedList L = this;
        if(possition>sizeOfList())    {
            return ERROR_CODE;
        }    else if(possition==1)    {
            return L.data;
        }    else    {
            for(int i=2; i<possition; i++)   
                L=L.next;
            return L.next.data;
        }
    }
   
    public void SwapPossitions(int a, int b)    {
        if(a>sizeOfList()||b>sizeOfList())    {
            System.out.println("Error Out of Bound Possition");
        }    else if(a==b)    return;
        else    {
            Replace(Replace(getValue(a), b), a);
        }
    }
   
    public void ReverseList()    {
        int half = sizeOfList()/2;
        for(int i=1; i<half; i++)    {
            SwapPossitions(i, (sizeOfList()-i+1));
        }
    }
}

No comments:

Post a Comment

UA-39217154-2