11 Java Intermediate Level Linked Lists Interview Questions & Answers

This interview question concentrates on the developer's skills working with Java linked lists and deletion.

You are given a sorted singly linked list. You need to remove the duplicates from the linked list and return its head node. The returned list must also be a sorted list.

/*Example*/

Given list- 1 -> 1 -> 2
expected output- 1 -> 2

Given list- 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4
expected output- 1 -> 2 -> 3 -> 4

Solution:

We will traverse the whole list. If we find a duplicate, we will delete it.
Let curr be the pointer to the current at which we are. It will point to the first occurrence of a number.
Let nextNode be the next node of curr.

We will compare the value of curr with the value of nextNode-
-> if the values are not equal, it means we don’t have any more duplicate corresponding to the value of curr, we will update curr to point to the next node.
-> if the values are equal, we will delete nextNode. We will delete nextNode by pointing next of curr to next of nextNode. So in the illustration below, curr is at 41 and nextNode is at 42. Their values are equal. So we will delete 42. We will point the next pointer of 41 to the next of 42 i.e. 43.

(The subscript shows the identity of nodes corresponding to the same value)

nextNode
|
0 -> 1 -> 2 -> 3 -> 41 -> 42 -> 43 -> 44 -> 5
| |
curr nextNode.next

After deleting nextNode (42)-
nextNode
|
0 -> 1 -> 2 -> 3 -> 41 -> 43 -> 44 -> 5
| |
curr nextNode.next

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        
        ListNode curr = head;
        
        while(curr != null && curr.next != null) {
            ListNode nextNode = curr.next;
            if (nextNode.val == curr.val) {
                // delete nextNode
                curr.next = nextNode.next;
            } else {
                curr = nextNode;
            }
        }
        return head;
    }
    
}

Time complexity- O(n)
Space complexity- O(1)

This interview question concentrates on the developer's skills working with Java linked lists, recursion, and iteration.

Given the head of a singly linked list, reverse the list, and return the reversed list.

/*Example*/

Given:  1 -> 2 -> 3 -> 4 -> 5
Expected output: 5 -> 4 -> 3 -> 2 -> 1

Solution:

Approach I (Recursive):

We maintain the current node and the node next to this node.
In our reverse() function we are taking the current node and the previous node as the input arguments. It reverses a singly linked list.

We continue to call the function with the node next to the head as the current node and the head as the previous node till we have reached the last node.

For 1 -> 2 -> 3 once we have reached the last node it would look like 1 -> 2 -> 3 -> null. Thus we need to make the last node point to the second last node. Which will make the list as 1 -> 2 <- 3.
Going back through our recursive calls we do the same reversing and return the last node as the root in the end.

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    public ListNode reverse(ListNode head, ListNode previous) {
        if(head == null) return null;
        
        ListNode curr = head;
        if (head.next != null) {
            curr = reverse(head.next, head);
        }
        head.next = previous;
        
        return curr;
    }
    
}

Time complexity- O(n) where n is the length of the list
Space complexity- O(n)

Approach II (Iterative):

We wish to maintain three variables. current, next, and prev.
During every iteration, we copy the node next to the head into our next variable. We need to save this before we move forward and reverse the current node.
Then we make the head node point to the previous node. With this, we are reversing our current node to point to the previous node.
Next, we assign the prev variable to the current node. Thus when we iterate forward in our list the node next to this can be pointed to this.
Finally, we assign the next to the current node so that we can iterate forward in our list and repeat the process for the next nodes.

Once we are done with all of the iterations we notice that the head variable is pointing to nothing. Thus we swap its value with the prev variable.

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode next = head;
        ListNode prev = null;
        
        while (current != null) {
            // Store next
            next = current.next;
            // Reverse current node's pointer
            current.next = prev;
            // Move pointers one position ahead.
            prev = current;
            current = next;
        }

        head = prev;
        return head;
    }
    
}

Time complexity- O(n) n is the length of the list
Space complexity- O(1)

This question focuses on working with Java lists.

You are given heads of two singly linked lists: headA and headB. Your task is to return the node at which they intersect each other. If they don’t intersect, return null.

It is guaranteed that there is no cycle in any of the lists. Please note the linked lists MUST retain their original structure after the function returns.

/*Example*/

Given lists:
headA: 			4 ->	1
					   \
						8 ->	7 ->	9
					   /
headB:	5 -> 	2 ->	3 ->	10
Expected output: 8
Explanation: Since both of the lists intersect at node 8, we return 8

Given lists:
headA:		4 ->	1 ->	8 ->	4 ->	5
headB: 	5 -> 	2 ->	3 ->	8 ->	4 ->	5
Expected output: null
Explanation: The lists do not intersect.

Solution:

Approach I (finding length)
First, we will find the lengths of the two lists using function listLength. Then we will align headA and headB such that the length of the list after points headA and headB is the same. For the first example:

lenA = 5
lenB = 7
We move headB two steps ahead to point to node with value 3 such that lengths after headA and headB are the same, that is 5.

After aligning the nodes, we iterate over both lists simultaneously and will find the same node. At each iteration, we advance both headA and headB if previous values were not equal. We break the loop as soon as the values of headA and headB are the same which means it is the intersection node.

If the lists do not intersect, the values of headA and headB will be null at last, which will break the loop and will return null.

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = listLength(headA);
        int lenB = listLength(headB);
    
        // if listA is of more length,
        // advance headA so that it aligns to headB
        while(lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        
        // if listB is of more length,
        // advance headB so that it aligns to headA
        while(lenB > lenA) {
            headB = headB.next;
            lenB--;
        }
    
        while(headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        
        return headA;
    }

    private int listLength(ListNode head) {
        int len = 0;
        while(head != null) {
            head = head.next;
            len++;
        }
        
        return len;
    }

}

n = length the linked list
Time complexity- O(n)
Space complexity- O(1)

Approach II (without finding the length):

In the previous approach, we found the lengths of the lists and then aligned them. In this approach, we will do this without actually finding the lengths of the lists.
Let's denote the two lists by list A and list B. Let’s take two pointers: pointer1 and pointer2. Pointer1 starts from the head of list A and pointer2 starts from the head of list B. In each step, we advance both the pointers one by one.

pointer1
|
A:- -------------
|----
B:- ------------------
|
pointer2

Since list A is shorter, pointer1 will reach the end first; we will point it to the head of list B and start advancing it in the same way.
A: -------------
|----
B: ------------------ |
| |
pointer1 pointer2

After some time, pointer2 will reach the end of list B; we will point it to the head of list A and start advancing it in the same way. At this point, pointer1 is traversing list B and pointer2 is traversing list A.
pointer2
|
A: -------------
|----
B: ------------------
|
pointer1

Now we will advance both pointers in the same way:- advance both pointers by one step simultaneously. In this type, both the pointer will reach the intersection at the same time. This will break the loop and will return the intersection node. If the lists do intersect, both pointers will be null at the end simultaneously, which will break the loop and return null.

Proof
Let us have two lists A and B with length len_a and len_b. Also assume list A is shorter than list B i.e., len_a < len_b

Let both the lists intersect each other and comm_len be the 1length of their common part.
|<====== len_a =====>|
A:- -----------------
|----
B:- ----------------------
|<==>| comm_len
|<======== len_b =========>|

When pointer1 reaches the end of list A, pointer1 and pointer2 have traversed len_a number of nodes.
When pointer2 reaches the end of list B, pointer1 and pointer2 have traversed len_b number of nodes. Or we can say that pointer1 traversed len_a number of nodes of list A and (len_b - len_a) number of nodes of list B; so total len_b number of nodes.

When both the pointers reach the intersection:

Number of nodes traversed by pointer1: len_a + (len_b - comm_len)
| |
of list A of list B
Number of nodes traversed by pointer1: len_b + (len_a - comm_len)
| |
of list B of list A
, which is the same. So both pointers are guaranteed to reach the intersection node during the second pass.

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, 
ListNode headB) {
        ListNode pointer1 = headA;
        ListNode pointer2 = headB;
    
        while(pointer1 != pointer2) {
            pointer1 = pointer1 == null ? headB : pointer1.next;
            pointer2 = pointer2 == null ? headA : pointer2.next;
        }
    
        return pointer1;
    }
    
}

n = length the linked list
Time complexity- O(n)
Space complexity- O(1)

This question focuses on Java iteration.

You are given a sorted linked list of positive numbers. The list contains some duplicate nodes. Your task is to remove all the duplicate nodes such that the final list contains only those numbers which occurred once in the original node. You need to do this in place and return the new head (if changed).

/*Example*/

Given list: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Expected list: 1 -> 2 -> 5

Given list: 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 3
Expected list: 3

Solution:

We will iterate over each node in the list. We will have two pointers: prev and curr. prev will point to the previous unique node.
2 -> 3 -> 3 -> 3 -> 4
| |
prev curr

In each iteration, we will compare the value of curr to the next of curr. If they are the same (means duplicates), we need to remove all the nodes with the same value altogether. We will iterate over each such duplicate node and reach the last node of the duplicate nodes. So, after such iterations, the pointers are:

2 -> 3 -> 3 -> 3 -> 4
| |
prev curr (curr is pointing to the last node of the duplicate nodes)

We will remove these duplicate nodes by changing the next pointer of prev (by doing prev.next = curr.next).

If the values of curr and next of curr are not equal, we just check the other nodes by moving prev and curr one step forward. In the code, we check if the values are equal or not by using the arrow function isNextNodeSame.

We use a dummy node (also called sentinel node) for this purpose. A dummy node is a placeholder node that is used to initialize a new linked list when we don't have the head node. It may be the case where the duplicates are starting from the head node. Such cases are difficult to handle without using a dummy node. We create a dummy node with the value 0 (since the minimum value in the given list is 1) with its next pointing to the head of the given list. This makes the list starting from a unique node and does not need special case handling.

1 -> 1 -> 3 -> 3 -> 4 (without dummy node)
0 -> 1 -> 1 -> 3 -> 3 -> 4 (with dummy node)

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    
    ListNode(int val) { this.val = val; }
   
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
    
        ListNode curr = head;
        ListNode prev = dummy;
    
        while (curr != null) {
            if (isNextNodeSame(curr)) {
                while (isNextNodeSame(curr)) {
                    curr = curr.next;
                }
                
                // we have reached the last of duplicate nodes
                // remove all these duplicate nodes
                prev.next = curr.next;
            } else {
                prev = prev.next;
            }
            
            curr = curr.next;
        }
        
        return dummy.next;
    }
    
    private boolean isNextNodeSame(ListNode curr) {
        return curr.next != null && curr.val == curr.next.val;
    }
}

n = number of nodes in the original list
Time complexity- O(n)
Space complexity- O(1)

This interview question focuses on the developer's ability to work with Java lists and partitions.

You are given a singly linked list. You are also given an integer x. Your task is to rearrange the list in such a way that all the nodes with values lesser than x occur before the nodes with values greater than or equal to x. You should preserve the relative order of the nodes.

/*Example*/

Given list: 1 -> 4 -> 3 -> 2 -> 5 -> 2		x = 3
Expected output: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Explanation: The nodes with a value less than 3 viz. 1, 2, 2 occur before with nodes with a value greater than or equal to 3 viz. 4, 3, 5. The relative order of all nodes remains the same, particularly focusing on 4, 3, 5. Please note that we need not sort the list.

Solution:

As we can see that there are two partitions of the list. We will create these two partitions separately and join them last. To avoid edge cases, we will create two dummy nodes (sentinel nodes) dummy1 and dummy2 for the two partitions. We will iterate over the given list. If the value of the current node is less than x, we append it to a list that contains lesser values, otherwise to the list which contains greater or equal values.

The two lists for the examples will be:
lesserCurr
|
dummy1 -> 1 -> 2 -> 2 -> null
dummy2 -> 4 -> 3 -> 5 -> (still points to last node 2)
|
greaterCurr

After finding these partitions, we join them. First of all, we set next of greaterCurr to null to avoid a loop because it may point to a node in the lesser partition (see the above example). After that, we join the two lists by setting next of lesserCurr to next of dummy2. The list becomes:

dummy1 -> 1 -> 2 -> 2 -> 4 -> 3 -> 5 -> null
Finally, we return dummy1.next.

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    
    ListNode(int val) { this.val = val; }
   
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode lesserCurr = dummy1;
        ListNode greaterCurr = dummy2;
        ListNode curr = head;
    
        while(curr != null) {
            if (curr.val < x) {
                lesserCurr.next = curr;
                lesserCurr = curr;
            } else {
                greaterCurr.next = curr;
                greaterCurr = curr;
            }
            
            curr = curr.next;
        }
    
        greaterCurr.next = null;
        lesserCurr.next = dummy2.next;
        return dummy1.next;
    }
    
}

n = length of length
Time complexity- O(n)
Space complexity- O(1)

This question focuses on the developer's skills with JavaScript lists and specific elements.

You are given a linked list. Your task is to delete those consecutive nodes which have the total sum of their values equal to zero. If there are many answers possible, return any.

/*Example*/

Given list: 1 -> 2 -> -3 -> 3 -> 1
Expected output: 3 -> 1
Note: 1 -> 2 -> 1 is also accepted.

Solution:

Let us assume we have a list [3, 4, 2, -6, 1, 1, 5, -6]. We calculate the prefix sums of the list. This will be [3, 7, 9, 3, 4, 5, 10, 4]. We can see that if a particular prefix sum occurs again (for example 3 here), the consecutive nodes between those two nodes have the sum equal to zero. We will store the prefix sums and corresponding in a map prefixSumMap. We will iterate over the whole list. In each iteration, we calculate the prefix sum (prefixSum) for the current node (curr). If it is not already present, we save the prefixSum in prefixSumMap and continue to the next node.

If the prefixSum is already present in the map, it means we already have seen the prefixSum in some previous node (prev). So we need to remove the nodes between that node and the current node.

list: 3 -> 4 -> 2 -> -6 -> 1 -> 1 -> 5 -> -6
prefixSum: 3 7 9 3 4 5 10 4
| |
prev curr

We will delete all the nodes between prev.next and curr (both inclusive). While deleting these nodes, we need to delete their prefix sums from prefixSumMap too. To do this, we start from deleteCurr = prev.next, iterate over this up to curr, calculate their prefix sums in newPrefixSum and delete the corresponding value from prefixSumMap. While doing so we don’t want to delete the prefixSum = 3 because we are not deleting node prev, so it should have its prefixSum in the newPrefixSum. This can be guarded using condition deleteCurr != curr. At last, we set prev.next to curr.next effectively deleting the required part of the list.

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    
    ListNode(int val) { this.val = val; }
   
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode curr = head;
        int prefixSum = 0;
        Map<Integer, ListNode> map = new HashMap<>();
        map.put(0, dummy);
    
        while (curr != null) {
            prefixSum += curr.val;
        
            if (!map.containsKey(prefixSum)) {
                map.put(prefixSum, curr);
                curr = curr.next;
                continue;
            }
        
            ListNode prev = map.get(prefixSum);
            ListNode deleteCurr = prev.next;
            int newPrefixSum = prefixSum;
        
            while (deleteCurr != curr) {
                newPrefixSum += deleteCurr.val;
                if (deleteCurr != curr) {
                    map.remove(newPrefixSum);
                }
                deleteCurr = deleteCurr.next;
            }
            
            prev.next = curr.next;
            curr = curr.next;
        }
        
        return dummy.next;
    }
    
}

n = length of length
Time complexity- O(n)
Space complexity- O(n)

This question shows the developer's skills working with Java nodes.

You are given the head node singly linked list and an integer k. Your task is to return the head of the linked list after swapping the kth node from the start and the kth node from the end (the list is 1-indexed).

/*Example*/

Given list: 1 -> 2 -> 3 -> 4 -> 5		k = 2
Expected list: 1 -> 4 -> 3 -> 2 -> 5

Given list: 1 -> 2 -> 3 -> 4 -> 5		k = 5
Expected list: 5 -> 2 -> 3 -> 4 -> 1

Given list: 1 -> 2 -> 3 -> 4 -> 5		k = 3
Expected list: 1 -> 2 -> 3 -> 4 -> 5

Solution:

NOTE: node(3) represents the node with a value equal to 3.
The first task is to find the nodes that need to be swapped. Since the head node can also be swapped, we will use a dummy node to deal with edge cases. Let’s say the list after adding dummy node (node(D)) is:

D -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

and let k = 3. Thus we need to swap nodes node(3) and node(6). To swap these nodes, we will need to manipulate the pointers of their previous nodes node(2) and node(5). So we need to find these pointers too. If we start with curr = dummy and we advance curr k = 3 times, it will point to node(3). So, to get the pointer to node(2), we will advance curr to k - 1 times. The pointer will after k - 1 times:

D -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
|
firstPrev and curr

Now, we will find the pointer to node(5). Let n be the number of nodes in the original list (here n = 8). If we start from node(0), we will reach node(5) in n - k = 5 steps. Also, if we start the curr at node(4), we reach the end of the list (that is null) in the same n - k = 5 steps. So we will point curr to node(4) and secondPrev to node(0) and start advancing both pointers. When we reach the end of the list, secondPrev will point to the required node, that is, node(5). The pointers before starting advancing:

D -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
| | |
secondPrev firstPrev curr

The pointers when curr reach the end of the list:

D -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
| | |
firstPrev secondPrev curr

After these two pointers, we can easily find the other required pointers:- first, second, firstNext and secondNext.

first second
| | |
D -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
| | | | |
firstPrev | secondPrev | curr
firstNext secondNext

Now comes the swapping part, there are four cases to consider:
1. When first and second are the same node:- It means no swapping at all.
2. When the first node is just after the second node:- The pointers will be like this:

second first firstNext
| | |
... -> [] -> [] -> [] -> [] -> ...
| | |
secondPrev firstPrev secondNext

Now we need to swap first and second. Thus the next of secondPrev should point to first; next of first should point to second; next of second should point to firstNext.
3. When the second node is just after the first node:- The pointers will be like this:

first second secondNext
| | |
... -> [] -> [] -> [] -> [] -> ...
| | |
firstPrev secondPrev firstNext

Now we need to swap first and second. Thus the next of firstPrev should point to second; next of second should point to first, and next of first should point to secondNext.
4. The other cases:- The pointers will be like this:

first second secondNext
| | |
... -> [] -> [] -> ... -> [] -> [] -> ...
|
firstPrev
OR
second first firstNext
| | |
... -> [] -> [] -> ... -> [] -> [] -> ...
|
secondPrev

Now we need to swap first and second. Thus the next of firstPrev should point to second; next of second should point to firstNext; next of secondPrev should point to first, and next of first should point to secondNext.

public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) { 
        this.val = val;
        this.next = next; 
    }
}

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode curr = dummy;
    
        for (int i = 1; i < k; i++) {
            curr = curr.next;
        }
        
        ListNode firstPrev = curr;
        curr = curr.next.next;
        ListNode secondPrev = dummy;
        
        while(curr != null) {
            curr = curr.next;
            secondPrev = secondPrev.next;
        }
        
        ListNode first = firstPrev.next;
        ListNode second = secondPrev.next;
        ListNode firstNext = first.next;
        ListNode secondNext = second.next;
        
        if (first == second) return dummy.next;
        else if (secondNext == first) {
            secondPrev.next = first;
            first.next = second;
            second.next = firstNext;
        } else if (firstNext == second) {
            firstPrev.next = second;
            second.next = first;
            first.next = secondNext;
        } else {
            firstPrev.next = second;
            second.next = firstNext;
            secondPrev.next = first;
            first.next = secondNext;
        }
        
        return dummy.next;
    }
}

n = number of nodes
Time complexity- O(n)
Space complexity- O(1)

This question allows the interviewer to see the developer's skills working with Java iterations.

You are given the head node of a linked list. For a node, the next greater node is the first node on the right side with a greater value. Your task is to compute the value of the next greater node for each node. If such a node does not exist for a particular node, consider 0 as the value of the next greater node.

/(Example*/

Given list: 	2 ->	7 ->	4 ->	3 ->	5
Expected output: [7, 0, 5, 5, 0]

Solution:

First of all, we will collect the values of all the nodes in an array. We will iterate over these values one by one. We will save these values in a stack. The stack contains the indices of the values for which we need to find the next greater value yet. For the current value, we will compare it with the top of the stack. If the top is smaller, it means the current value is the next greater value for the top of the stack.

We will pop this top and save the value in the answer array. We will do this recursively until we find the next greater value for all the values. The answer array is already filled with 0 for those values that don’t have their next greater value.

public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { this.val = val; }
    
    ListNode(int val, ListNode next) { 
        this.val = val;
        this.next = next; 
    }
}

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        ArrayList<Integer> nodeValues = new ArrayList<>();
        ListNode curr = head;
    
        while(curr != null) {
            nodeValues.add(curr.val);
            curr = curr.next;
        }
        
        int answer[] = new int[nodeValues.size()];
        Stack<Integer> stack = new Stack<>();
    
        for (int i = 0; i < nodeValues.size(); i++) {
            while (isTopSmaller(stack, nodeValues, i)) {
                int idx = stack.pop();
                answer[idx] = nodeValues.get(i);
            }
            
            stack.push(i);
        }
        
        return answer;
    }
    
    private boolean isTopSmaller(
        Stack<Integer> stack, 
        ArrayList<Integer> nodeValues,
        int idx
    ) {
        if (stack.empty()) return false;
        return nodeValues.get(stack.peek()) < nodeValues.get(idx);
    }
    
}

n = number of nodes
Time complexity- O(n)
Space complexity- O(n)

This question focuses on the developer's ability to work with Java iterations.

You are given the head of a linked list that contains distinct integer values. You are also given array nums which is a subset of the values in the linked list (in any order).

Your task is to return the number of connected components in nums, where two values are connected if they appear consecutively in the list.

/*Example*/

Given list:	0 ->	1 ->	2 ->	3	nums = [0, 1, 3]
Expected output: 2
Explanation: The connected components are [0, 1] and [3]. Thus two connected components.

Given list:	0 -> 1 ->	2 ->	3 ->	4	nums = [0, 3, 1, 4]
Expected output: 2
Explanation: The connected components are [0, 1] and [3, 4]. Thus two connected components.

Solution:

We will iterate over the whole linked list. If the current node is in nums, we will increase the final answer by 1, and skip all of the next nodes which are in nums. To check if the node is in nums, we will use a set.

public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { this.val = val; }
    
    ListNode(int val, ListNode next) { 
        this.val = val;
        this.next = next; 
    }
}

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums) set.add(num);
        int count = 0;
        
        ListNode curr = head;
        
        while(curr != null) {
            if (!set.contains(curr.val)) {
                curr = curr.next;
                continue;
            }
            
            count++;
            while (curr != null && set.contains(curr.val)) {
                curr = curr.next;
            }
        }
        
        return count;
    }
    
}

n = number of nodes
Time complexity- O(n)
Space complexity- O(n)

This question allows the interviewer to see the developer's skills working with Java arrays.

You are given the head of a singly linked list. You are also given a positive integer k. Your task is to split the list into k parts following the rules:

1. The length of each part should be as equal as possible.
2. Some parts may be null.
3. The relative order of the parts and the nodes in the parts should be the same as the given list.
4. No two parts can have a difference in their length of more than 1.
5. The parts with greater length should occur before the parts with a smaller length.
You need to return the array of size k containing the heads of the parts.

/*Example*/

Given list:	1 ->	2 ->	3	k = 5
Expected output:	[[1], [2], [3], [], []]
Explanation: The last two parts are a list of length 0, that is, their heads are null. The length of the rest of the parts can be at most 1. They occur before the parts with 0 lengths. The relative order of the nodes is the same as the given list.

Given list:	1 ->	2 ->	3 ->	4 ->	5 ->	6 ->	7	k = 3
Expected output:	[[1, 2, 3], [4, 5], [6, 7]
Explanation: The difference in lengths between any two parts is at most 1. The greater part occurs before the smaller parts.

Solution:

First of all, we will find the length of the list. Then we will find the length of each part and the remaining nodes represented by the variables partLen and remNodes. We create an answer array of parts of size k which will store the head nodes of the parts.

We will distribute the remNodes on the earlier parts, one for each part. Thus, if there are still some remNodes left, the length of the current part will be partLen + 1, otherwise, it will be partLen.
The last node of each node should not point to any node, that is, we will set the next pointer of lastNode to null.

public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { this.val = val; }
    
    ListNode(int val, ListNode next) { 
        this.val = val;
        this.next = next; 
    }
}

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int len = findListLength(head);
        ListNode parts[] = new ListNode[k];
        Arrays.fill(parts, null);
        int partLen = len / k;
        
        int remNodes = len % k;
        ListNode curr = head;
        
        for (int i = 0; curr != null && i < k; i++, remNodes--) {
            parts[i] = curr;
            ListNode lastNode = curr;
            int currPartLen = partLen + (remNodes > 0 ? 1 : 0);
            
            for (int j = 0; j < currPartLen; j++) {
                lastNode = curr;
                curr = curr.next;
            }
            
            lastNode.next = null;
        }
        
        return parts;
    }
    
    private int findListLength(ListNode head) {
        int len = 0;
        while(head != null) {
            len++;
            head = head.next;
        }
        
        return len;
    }
    
}

n = number of nodes
Time complexity- O(n)
Space complexity- O(1)

This question shows the developer's skills working with Java lists and iterations.

You are given the head node of the linked list. The first node is considered as the odd node, the second node is considered as an even node, and so on. Your task is to modify the list such that all the odd nodes occur before all the even nodes and their relative order is the same as in the given list. Return the head of the modified list.

/*Example*/

Given list:	1 ->	2 ->	3 ->	4 ->	5
Expected output list:	1 ->	3 ->	5 ->	2 ->	4

Given list:	2 ->	1 ->	3 ->	5 ->	4 ->	6
Expected output list:	2 ->	3 ->	4 ->	1 ->	5 ->	6

Solution:

The solution is pretty simple. We will maintain two lists: odd and even. Then we will iterate over the given list and update pointer odd and even accordingly. In the end, we update the next pointer of the last node in the odd list to the head of the even list.

public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { this.val = val; }
    
    ListNode(int val, ListNode next) { 
        this.val = val;
        this.next = next; 
    }
}

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
    
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
    
        while(even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            
            even.next = odd.next;
            even = even.next;
        }
        
        odd.next = evenHead;
        return head;
    }

}

n = number of nodes
Time complexity- O(n)
Space complexity- O(1)