Question

What will be the final linked-list after executing the following method on the given input singly linked-list? Consider that the singly linked-list does not have a tail reference.

Input: 1->2->3->4->5->6->7->8->null                                                   

void method(list){

if(list.head == null) return;

Node slow_ref = list.head;

Node fast_ref = list.head;

Node prevS = null;

Node prevF = null;

while(fast_ref != null && fast_ref.next != null){

prevS = slow_ref;

slow_ref = slow_ref.next;

prevF = fast_ref;

fast_ref = fast_ref.next.next;

}

prevS.next = slow_ref.next;

prevF.next.next = slow_ref;

slow_ref.next = null;

}

Answer 1

Here we are re-adjusting the pointers to modify the linked list.

slow_ref is 5 and prevS is 4

fast_ref is null and prevF is 7

After adjusting the links, linked list is

1->2->3->4->6->7->8->5->NULL

i.e slow pointer is moved at the end of the linked list

Program Execution

class LinkedList{
    Node head;
    void add(int i){
        Node newNode= new Node(i);
        if(head==null){
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next!=null){
            temp = temp.next;
        }
        temp.next = newNode;
    }

    void print(){
        Node tem = head;
        while(tem!=null){
            System.out.print(tem.item+"->");
            tem = tem.next;
        }
        System.out.println("NULL");
    }
}
class Main{

    static void method(LinkedList list){
        if(list.head == null) return;
        Node slow_ref = list.head;
        Node fast_ref = list.head;
        Node prevS = null;
        Node prevF = null;
        while(fast_ref != null && fast_ref.next != null){
            prevS = slow_ref;
            slow_ref = slow_ref.next;
            prevF = fast_ref;
            fast_ref = fast_ref.next.next;
        }

        prevS.next = slow_ref.next;
        prevF.next.next = slow_ref;
        slow_ref.next = null;
    }


    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        for(int i=1;i<=8;i++){
            ll.add(i);
        }
        ll.print();
        method(ll);
        ll.print();
    }
}

Output