Question

Implement a CircularDoubleLinkedList.The removelast method should be implemented with O(1) complexity. There rest is just to keep all pointers correct. (Implement in Java pls)

Answer 1

With a time complexity of O(n)

and space complexity of O(1)

class remLast { 
    static class Node { 
        int data; 
        Node next; 
    }; 
  
    static Node remLNode(Node head) 
    { 
        if (head == null) 
            return null; 
  
        if (head.next == null) { 
            return null; 
        } 
  
      
        Node sec_Last = head; 
        while (sec_Last.next.next != null) 
            sec_Last = sec_Last.next; 
  
       
        sec_Last.next = null; 
  
        return head; 
    } 
    static Node push(Node head_Ref, int new_Data) 
    { 
        Node new_Node = new Node(); 
        new_Node.data = new_Data; 
        new_Node.next = (head_Ref); 
        (head_Ref) = new_Node; 
        return head_Ref; 
    } 
  
    // driver code 
    public static void main(String args[]) 
    { 
        Node head = null; 
        head = push(head, 12); 
        head = push(head, 29); 
        head = push(head, 11); 
        head = push(head, 23); 
        head = push(head, 8); 
  
        head = remLNode(head); 
        for (Node temp = head; temp != null; temp = temp.next) 
            System.out.print(temp.data + " "); 
    } 
}