Basic Linked List Operation

LinkedListBasic.java

class Node {
    
    int data;
    Node next;
    
    Node(int d)  
    { 
        data = d;  
        next = null; 
    } 
}

class LinkedList
{
    Node head;  // head of list
 
    /* This function prints contents of linked list starting from head */
    public void printList()
    {
        Node temp = head;
        System.out.println( " Print Function ");
        while (temp != null)
        {
            System.out.println( "   Data: " + temp.data);
            temp = temp.next;
        }
    }
    
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
 
        llist.head   = new Node(1);
        Node second  = new Node(2);
        Node third   = new Node(3);
        Node fourth  = new Node(4);
        Node fifth   = new Node(5);
        
        llist.head.next = second;
        second.next = third;
        third.next  = fourth;
        fourth.next = fifth;
        llist.addAtEnd(6);
        llist.addAtEnd(7);
        llist.addAtEnd(8);
        
        llist.printList();
        
        llist.deleteNafterM();
        // create a loop here
        // fifth.next  = third;
        llist.printList();
        // llist.rotate(3);
        // llist.printList();
        
    }
    
    public void deleteNafterM()
    {
        Node temp = this.head;
        Node prev = null;
        int m = 2;
        int n = 2;
        int ic = 0;
        int dc = 0;
        
        while(temp!=null)
        {
            if(ic< (m))
            {
                ic++;
                prev = temp;
                temp = temp.next;
                continue;
            }
            else
            {
                ic = 0;
            }
            //System.out.println( " Shifting to delete prev Data: " + prev.data);
            //System.out.println( " Shifting to delete temp Data: " + temp.data);
            while(dc < (n) && temp !=null)
            {
                temp = temp.next;
                dc++;
            }
            // System.out.println( " End Data: " + temp.data);
            prev.next = temp;
            dc = 0;
        }
    }
    
    public void rearrangeEvenOddPositionNode()
    {
        Node even = this.head;
        Node odd  = this.head.next;
        
        //start position of second list
        Node temp = odd; 
        
        while(even.next!=null)
        {
            if (odd.next == null)
            {
                break;
            }    
            even.next = even.next.next;
            even      = even.next;
            odd.next  = odd.next.next;
            odd       = odd.next;
        }
        even.next = temp;
    }
        
    public void reverseRecursive()
    {
        Node temp = this.head;
        reverseRecursiveHelper(temp);
    }
    
    public void reverseRecursiveHelper(Node temp)
    {
        if(temp.next == null){
            this.head = temp;
            return;
        }
        reverseRecursiveHelper(temp.next);
        // if we add a node at the end we are creating new node to impplement the reverse function
        // addAtEnd(temp.data);
        // to just re-arrange the node to reverse the we interchange the nodes
        Node q = temp.next;
        q.next = temp;
        temp.next = null;
    }
    
    public void reverse()
    {
        Node current, prev = null, next = null;    
        current = this.head;
        while(current!=null)
        {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        this.head = prev;
    }
    
    public void rotate(int k)
    {
        Node temp = this.head;
        Node prev = null;
        // we do a k-1
        // if we count from c = 0, then count is 0 based
        // but we see k as 1 based. 
        int c = 0;
        while(temp!=null && c < k-1)
        {
            c++;
            prev = temp;
            temp = temp.next; 
        }
        
        System.out.println(" temp data " + temp.data);
        // System.out.println(" prev data " + prev.data);
        
        Node midStart = temp;
        while(midStart.next!=null)
        {
            midStart = midStart.next;
        }
        midStart.next = this.head;
        prev.next = null;
        this.head = temp.next;
    }
    
    public void deleteAlternateNode()
    {
        Node temp = this.head;
        while(temp !=null && temp.next !=null)
        {
            temp.next = temp.next.next;
            temp = temp.next;
        }
    }
    
    public void removeInSorted()
    {
        // we assume that the list given is sorted
        Node temp = this.head;
        while(temp.next !=null)
        {
            if(temp.data == temp.next.data)
            {
                temp.next = temp.next.next;
            }
            else
            {
                temp = temp.next;
            }
        }
    }
    
    public void insertInSortedList(int key)
    {
        // insert in sorted position assuming the list is sorted    
        Node temp = this.head;
        Node prev = this.head;
        Node newNode = new Node(key);
        
         
        // if LL is empty, then newNode is the head
        // if key is smaller then head, insert at head
        if(temp == null || temp.data > key)
        {
            newNode.next = head;
            head = newNode;
            return;
        }
        
        
        while(temp!=null && temp.data < key)
        {
            prev = temp;
            temp = temp.next;
        }
        
        
        newNode.next = prev.next;
        prev.next    = newNode;
        
    }
    
    public void detectAndRemoveLoop()
    {
        Node slow   = this.head; 
        Node fast   = this.head;
        
        while(fast!=null && fast.next !=null)
        {
            slow = slow.next;
            fast = fast.next.next;
            if( slow == fast) 
            {
                break;
            }
        }
        
        if(slow != fast)
        {
            System.out.println("No Loop");
            return;
        }    
        
        System.out.println(" Loop detected. Trying to remove the loop..... ");
        
            
        slow = this.head;
        while (slow.next != fast.next) 
        {
          slow = slow.next;
          fast = fast.next;
        }
        System.out.println("Loop starts at: " + fast.next.data);
        fast.next = null;
    }
        
    public void getNthNodeFromEnd(int pos )
    {
        // Print the (len – n + 1)th node from the begining of the Linked List.
        Node temp = this.head;
        int l = 0;
        while(temp!=null)
        {
            l++;
            temp = temp.next;
        }
        
        int c = 0;
        int n = l - pos + 1;
        
        System.out.println( " Length " + l);
        System.out.println( " Position " + pos);
        
        if( pos > l)
        {
            System.out.println(" Position greater than lenght of List");
            return;
        }
        
        temp = this.head;
        while( temp !=null)
        {
            c++;
            if (c == n)
            {
                break;
            }
            temp = temp.next;
        }
        System.out.println(temp.data);
    }
    
    public void getMiddleNode()
    {
        // Move one pointer by one and other pointer by two. 
        // When the fast pointer reaches end slow pointer will reach middle
        Node slow   = this.head; 
        Node fast   = this.head;
        
        while(fast!=null && fast.next !=null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        System.out.println(slow.data);
    }
    
    public void getNthNode(int pos)
    {
        Node temp    = this.head;
        Node prev    = null; 
        int curr_pos = 0;
        if(pos == 0)
        {
            System.out.println( pos + " Node data :" + temp.data);
            return;
        }
        while(temp!=null)
        {
            prev = temp;
            temp = temp.next;
            curr_pos++;
            if (curr_pos == pos )
            {
                break;
            }
        }
        if( temp == null)
        {
            System.out.println( pos + " does not exists in LL ");
            return;
        }
        System.out.println( pos + " Node data :" + temp.data);
    }
    
    public void search(int key)
    {
        Node temp = this.head;
        while(temp != null)
        {
            if( temp.data == key)
            {
                System.out.println(" Data Found ");
                return;
            }
            temp = temp.next;
        }
        System.out.println(" Data Not Found ");
    }    
    
    public void searchRecursive(int key)
    {
        Node temp = this.head;
        System.out.println(" found " + this.searchRecursiveHelper(temp, key));   
    }   
    
    public boolean searchRecursiveHelper(Node temp, int key)
    {
        if (temp == null) 
        {
            return false;
        }
        if (temp.data == key)
        {
            return true;
        }
        return searchRecursiveHelper(temp.next, key);
    }   
    
    public void length()
    {
        Node temp = this.head;
        int l = 0;
        while (temp != null)
        {
            l++;
            temp = temp.next;    
        }    
        System.out.println(" Iterative Length " + l);
    }
    
    public void lengthRecursive()
    {
        Node temp = this.head;
        int l = this.lengthHelper(temp);    
        System.out.println(" Recursive Length " + l);
    }
    
    public int lengthHelper(Node temp)
    {
        if (temp == null) 
        {
            return 0;
        }
        return 1 + this.lengthHelper(temp.next);
    }
    
    public void deleteAtPosition(int pos)
    {
        // current_pos and position are both 0 index. Obvious. 
        Node temp = this.head;
        Node prev = null;
        int current_pos = 0;
        
        if(temp == null)
        {
            System.out.println(" Linked List Is empty");
            return;  
        }
        
        // check in head node for node to be deleted
        if(pos == 0)
        {
            this.head = temp.next;
            return;
        }
        
        // The loop will break: 
        //  1. when LL has ended before position has reached
        //    So no such pos exists. Throw error.
        //  2. position has reached
        while (temp != null)
        {
            prev = temp;
            temp = temp.next;
            current_pos ++;
            if( current_pos == pos)
            {
                break;
            }
        }
        
        if(temp == null)
        {
            System.out.println(" No such node positon " + pos);
            return;
        }
        
        prev.next = temp.next;
        return;
    }
    
    public void deleteNode(int data)
    {
        Node temp = this.head;
        Node prev = null;
        
        if(temp == null)
        {
            System.out.println(" Linked List Is empty");
            return;  
        }
        
        // check in head node for node to be deleted
        if(temp.data == data)
        {
            this.head = temp.next;
            return;
        }   
        
        while(temp != null)
        {
            if (temp.data == data)
            {
                break;
            }
            prev = temp;
            temp = temp.next;
        }
        
        if(temp == null)
        {
            System.out.println(" Data does not exits"); 
            return;
        }
        if(temp.data == data)
        {
            prev.next = temp.next;
            return;
        }
        return;
        
    }
    
    public void addAtHead(int data)
    {
        Node node  = new Node(data);
        node.next  = this.head;
        this.head  = node;
    }
    
    public void addAtEnd(int data)
    {
        Node node  = new Node(data);
        Node temp  = this.head;
        
        // find the tail node
        while(temp.next != null)
        {
            temp = temp.next;
        }
        
        temp.next = node;
    }
    
    
    public void addAfterValue(int after, int data)
    {
        // create new node
        Node node  = new Node(data);
        Node temp  = this.head;
        
        if ( temp == null)
        {
            System.out.println(" LL is empty ");
            return;
        }
        
        // while takes care if data needs to be added after head - no spl case required
        // temp will fetch the node after which the data has to be added if such a data exists
        while (temp.next != null)
        {
            // the node found. break now.
            if( temp.data == after) 
            {
                break;   
            }
            temp = temp.next;
        }
        
        // case when data needs to be added after last node
        if( temp.next == null && temp.data == after )
        {
            temp.next = node; 
            return;
        }
        else if(temp.data == after)
        {
           // normal middle node in linked list
           Node transfer = temp.next;
           temp.next = node;
           node.next = transfer;
           return;
        }
        
        // hanlde case if no such data exists
        System.out.println(" No such data node exists");
    }
    
    
    public void addAtPosition(int position, int data)
    {
        int count  = 0;
        Node node  = new Node(data);
        Node temp  = this.head;
        Node prev  = null;
        
        if (this.head == null)
        {
            // this might be the first node in the LL
            this.head = node;
            return;
        }
        
        if(position == 0)
        {
          // add at head
          this.addAtHead(data);  
          return;  
        }
        
        // find the tail node
        while(temp.next != null && count < (position+1))
        {
            count++;
            prev = temp;
            temp = temp.next;
        }
        
        if(count < (position+1))
        {
            System.out.println("Invalid Position.Linked List is shorter.");
            return;
        }         
        
        if(prev !=null)
        {
            node.next = prev.next;
            prev.next = node;
        }
    }
    
    public void test()
    {
        Node temp = this.head;
        Node prev = null;
        while(temp.next!=null)
        {
            prev = temp;
            temp = temp.next;
        }
        System.out.println( "Prev data " + prev.data);
        System.out.println( "Prev next " + prev.next);
        System.out.println( "Temp " + temp.data);
    }
}