Answer to Question #300580 in Java | JSP | JSF for Akash Srivastava

Question

Given a linked list, the task is to move all 0’s to the front of the linked list. The order of all another element except 0 should be same after rearrangement.

Note: Avoid use of any type of Java Collection frameworks.

Note: For custom input/output, enter the list in reverse order, and the output will also be in reverse order.

Input

User Task:

Since this will be a functional problem, you don't have to take input. You just have to complete the function moveZeroes() that takes head node as parameter.

Constraints:

1 <= T <= 100

1 <= N <= 100000

0<=Node.data<=100000

Note:- Sum of all test cases doesn't exceed 10^5

Output

Return the head of the modified linked list.

Answer 1

public class Main {
    public static Node moveZeroes(Node head) {
        Node newHead = null;
        Node currentHead = null;
        Node tail = null;
        Node currentTail = null;
        for (; head != null; head = head.next) {
            if (head.data == 0) {
                if (newHead == null) {
                    newHead = new Node(head.data);
                    currentHead = newHead;
                } else {
                    currentHead.next = new Node(head.data);
                    currentHead = currentHead.next;
                }
            } else {
                if (tail == null) {
                    tail = new Node(head.data);
                    currentTail = tail;
                } else {
                    currentTail.next = new Node(head.data);
                    currentTail = currentTail.next;
                }
            }

        }
        if (currentHead != null) {
            currentHead.next = tail;
        }
        return newHead != null ? newHead : tail;
    }  
}