Sunday, June 15, 2014

Reverse a linked list


java code to create single linked list
 
//This is linked list node structure
class LinkedList{
    public int data;
    public LinkedList link;
    public LinkedList(int data) {
        this.data = data;
    }
}

public class LinkedListReverse {
    LinkedList node,start = null, end = null;
    public static void main(String[] args) throws InterruptedException {
        LinkedListReverse linkedListReverse = new LinkedListReverse();
        linkedListReverse.insert(50);
        linkedListReverse.insert(40);
        linkedListReverse.insert(56);
        linkedListReverse.insert(53);
        linkedListReverse.insert(23);
        linkedListReverse.insert(11);
        linkedListReverse.traverse();
        System.out.println("Reverse Linked List");
        linkedListReverse.reversePrint(linkedListReverse.getFirstNode());
        linkedListReverse.reverseLinkedList(linkedListReverse.getFirstNode());
        System.out.println("**********************");
        linkedListReverse.traverse();
    }
   
// This method insert new node to existing linkedlist
private void insert(int record){
        node = new LinkedList(record);
        if(start == null){
            node.link = start;
            start =node;
        }
        else{
            end.link= node;
        }
        end =node;
}

 /*Prints the linkedlist in reverse order using recursion but there is no change in binding of node */
private void reversePrint(LinkedList linkedList) throws InterruptedException{
        if(linkedList.link != null){
            reversePrint(linkedList.link);
        }
        System.out.println(linkedList.data);
    }



// reverse the linked list in reverse order. This method changes the binding of node.
LinkedList preStart = null;
private void reverseLinkedList(LinkedList linkedList){
        if(linkedList.link.link != null)
            reverseLinkedList(linkedList.link);
        else if(linkedList.link.link == null){
            preStart = getFirstNode();
            start = linkedList.link;
            start.link = null;
        }
        linkedList.link.link = linkedList;
        if(linkedList == preStart)
            linkedList.link = null;
    }

No comments:

Post a Comment