Answer to Question #216562 in Java | JSP | JSF for Shivam Yadav

Question

In a hypothetical server, we have a list of tasks arranged in the form of a doubly linked list. In this list in addition to the next and previous pointer each node also has a tertiary pointer, which represents some cleanup tasks required before moving on to the 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. Also Analyse the running time of the algorithm for the given ‘n’ being the number of tasks

Answer 1

public static Node reorganize(Node head) {
    Node cur = head;
    Node node = null;
    while (cur != null) {
        node = new Node(cur.task.data);
        node.prev = cur;
        node.next = cur.next;
        cur.next = node;
        node.next.prev = node;
        cur = node.next;
    }
    tail = node;
    return head;
}

Complexity O(n)