Answer to Question #216717 in Java | JSP | JSF for Anonymous

Question

In a hypothetical server, we have a list of tasks arranged in form of a doubly linked list. In this list in addition to next and previous pointer each node also has a tertiary pointer, which represents some cleanup tasks required before moving on to next tasks of the list. The current scheduler however does not recognize this list structure. Your task is to implement an algorithm that takes input the head of the doubly linked list with nodes having a tertiary pointer and gives the head of a rearranged doubly linked list with all tasks arranged linearly (with nodes having just the next and previous pointers only, no tertiary pointer). The modifications should be in-place, that means you cannot change the contents (other than next and previous pointer)  or the address of any of the nodes. Analyse the running time of the algorithm for the given ‘n’ being the number of tasks. 

(For algorithm, write the pseudo code and explain the logic, write base cases and sub problems too)

Answer 1

public class Sche {
    Node head; 
    class Node {
        int data;
        Node prev;
        Node next;
        Node(int d) { data = d; }
    }
    public void push(int new_data)
    {
        Node new_Node = new Node(new_data);
        new_Node.next = head;
        new_Node.prev = null;
 
        if (head != null)
            head.prev = new_Node;
 
        head = new_Node;
    }
 
    public void InsertAfter(Node prev_Node, int new_data)
    {
        if (prev_Node == null) {
            System.out.println("The given previous node cannot be NULL ");
            return;
        }
        Node new_node = new Node(new_data);
        new_node.next = prev_Node.next;
        prev_Node.next = new_node;
        new_node.prev = prev_Node;
        if (new_node.next != null)
            new_node.next.prev = new_node;
    }
    void append(int new_data)
    {
        Node new_node = new Node(new_data);
 
        Node last = head; 
        new_node.next = null;
        if (head == null) {
            new_node.prev = null;
            head = new_node;
            return;
        }
        while (last.next != null)
            last = last.next;
        new_node.prev = last;
    }
    public void printlist(Node node)
    {
        Node last = null;
        System.out.println("Traversal in forward Direction");
        while (node != null) {
            System.out.print(node.data + " ");
            last = node;
            node = node.next;
        }
        System.out.println();
        System.out.println("Traversal in reverse direction");
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.prev;
        }
    }
 
    public static void main(String[] args)
    {
        Sche  s= new Sche();
 
        
    }
}