9 Java Beginner Level Linked Lists Interview Questions & Answers

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

You are given two numbers that are represented as two singly-linked lists. Each node of the linked list represents a digit in the number. The digits are stored in reverse order. That is, the unit-place digit is the head of the linked list. Your task is to find the sum of the two numbers and return the result in the form of a linked list.

/*Example*/

Let two numbers are 123 and 456
so given linked lists will be
	3 -> 2 -> 1
and	6 -> 5 -> 4

The sum of the numbers is 579
So the expected result will be
	9 -> 7 -> 5

Constraints:  The numbers of nodes in each given linked lists will be between 1 and 100

Solution:

The first solution that comes to mind is to get the value numbers from given linked lists. Then add them, and then create a linked list from the result again.

But the number of the digits in the list is up to 100, which means the range of the numbers is [1, 10100], which is too large for storing numbers directly in their bit forms in a computer.

What we can do is take digits one by one from the linked lists and add them. If it is smaller than 10, directly append it to the resultant list; if it is greater than 10, then append its unit place to the list and forward carry 1 to the next digits as we do in pen-paper while adding two numbers.

More formally,
Let, a and b are the linked lists and res be result list.
ai and bi are digits stored in the ith node.

ri = ai + bi + ci - 1 // take carry from last calculation
resi = ri % 10 // store the unit place i.e. remainder by 10
ci = floor(ri / 10) // forward carry, if any

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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        int carry = 0;
        ListNode a = l1;
        ListNode b = l2;
        ListNode currRes = res;
        
        while(a != null || b != null) {
            // if either a or b are null i.e. length of one number
            // is greater than other, then assume(extend) 0
            // at other places
            int digitA = (a != null) ? a.val : 0;
            int digitB = (b != null) ? b.val : 0;
            
            int r = digitA + digitB + carry;
            
            ListNode node = new ListNode(r % 10);
            carry = r / 10;
            currRes.next = node;
 
            currRes = currRes.next;
            a = (a != null) ? a.next : null;
            b = (b != null) ? b.next : null;
        }
        
        // if there is carry at the end. It means
        // addition of most significant digits of given numbers
        // is greater than 10. E.g a = 999, b = 999
        if (carry > 0) {
            ListNode node = new ListNode(carry);
            currRes.next = node;
        }
        
        return res.next;
    }
    
}

Time complexity - O(max(n, m)) // n and m are length of the two digits
Space complexity - O(1)

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

You are given a linked list. You need to return the middle node of the linked list. If there are two middle nodes (the list is of even size), then return the second node.

/*Example*/

Given list- 1 -> 2 -> 3 -> 4 -> 5
expected returned node- 3

Given list- 1 -> 2 -> 3 -> 4 -> 5 -> 6
expected returned node- 4

Solution:

The solution is quite simple. We will count the total number of nodes in the list. Then we will find the index of the middle element by dividing it by 2.

Let nodeCount be total number of nodes
if nodeCount is odd,
middle element is at index floor(nodeCount / 2)
for example, if nodeCount = 5, middle element element is at index floor(5 / 2) = 2
if nodeCount is even,
middle element is at index nodeCount / 2
for example, if nodeCount = 6, middle element element is at index 6 / 2 = 3

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 middleNode(ListNode head) {
        if (head == null) return null;
        
        int nodeCount = 0;
        ListNode curr = head;
        
        while(curr != null) {
            nodeCount++;
            curr = curr.next;
        }
        
        int mid = (int) Math.floor(nodeCount / 2);
        
        curr = head;
        for (int i = 1; i <= mid; i++) {
            curr = curr.next;
        }
    
        return curr;
    }

}

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

This question focuses on Java recursion and iteration.

You are given the head of a linked list. You are also given a target value. Your task is to remove all the nodes from the linked list whose value is equal to the target.

/*Example*/

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

Solution:

Approach I (recursive):

In the recursive approach, we will check the value of the current node in the function call. If the value of the current node i.e. head in the function call is equal to target, we return next of head instead of returning head. Before doing that, we recursively check and remove the next head. For example: for list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, the calls are:

(rm denotes the function removeElements)
|rm(1)
| |rm(2)|
| | |rm(6)|
| | | |rm(3)|
| | | | |rm(4)|
| | | | | |rm(5)|
| | | | | | |rm(6)|
| | | | | | | |rm(null)
| | | | | | | | return null
| | | | | | | |head.next = null
| | | | | | | |head.val == 6; // 6 == 6 => true
| | | | | | | |return head.next(null)
| | | | | | |head.next = null
| | | | | | |head.val == 6; // 5 == 6 => false
| | | | | | |return head(5)
| | | | | |head.next = 5
| | | | | |head.val == 6 // 4 == 6 => false
| | | | | |return head(4)
| | | | |head.next = 4
| | | | |head.val == 6 // 3 == 6 => false
| | | | |return head(3)
| | | |head.next = 3
| | | |head.val == 6 // 6 == 6 => true
| | | |return head.next(3)
| | |head.next = 3
| | |head.val == 6 // 2 == 6 => false
| | |return head(2)
| |head.next = 2
| |head.val == 6 // 1 == 6 => false
| |return head(1)
The resulting list is the return of all the function calls i.e. 1 -> 2 -> 3 -> 4 -> 5

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 removeElements(ListNode head, int val) {
        if (head == null) return null;
 
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;

    }
}

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

Approach II (iterative):

In the iterative approach, we loop over all the nodes in the list. From the current node curr, if it has a next node (curr.next) and its value is equal to the target, we will remove the next node. To remove we will set next of curr to next of curr.next.
After the loop, all the nodes with value target will be removed except at the head. So after the loop, we will check for the head node too.

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 removeElements(ListNode head, int val) {
        if (head == null) return null;
        
        ListNode curr = head;
        while(curr != null && curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
    
        // the first node
        if (head.val == val) head = head.next;
        
        return head;
    }
    
}

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

This question focuses on Java iteration.

You are given a node nodeToDelete of a singly linked list. Your task is to delete this node. This is guaranteed that the given node will not be the tail node of the linked list. Please note that you are not given the head of the linked list. You don’t have to return anything, just update the list in place.

/*Example*/

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
                        |
                        given node
Expected output list:- 1 -> 2 -> 4 -> 5 -> 6 -> 7

Solution:

We will iterate over all the nodes after nodeToDelete. Let curr be the current node. We will copy the value of the next to the current node. Thus the value of the node to be deleted will be replaced with the value of the next node. For example the given list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 and 3 be the node to be deleted:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 6 -> 7
|
curr

When we are the second last node (i.e. curr.next.next is null), we will copy the value of the last node and then we will delete the last node by setting curr.next = null.

1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 7 (copy)
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 7 (delete last 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 void deleteNode(ListNode node) {
        ListNode curr = node;
    
        while(true) {
            // copy value of next node
            curr.val = curr.next.val;
 
            // curr is the second last node
            // curr.next is the last node
            // delete it, and break loop
            if (curr.next.next == null) {
                curr.next = null;
                break;
            }
            
            curr = curr.next;
        }
    }
    
}

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

This interview question focuses on the developer's ability to use Java iteration.

You are given two sorted singly-linked lists. Your task is to merge both linked lists and return them to a new linked list.

/*Example*/

Given: l1 = [1, 3, 4]		l2 = [2, 5, 6]
Expected output: [1, 2, 3, 4, 5, 6]

Solution:

We will iterate over all the nodes of the lists. We will have two pointers curr1 and curr2 pointing to the current nodes we are processing for both the lists. We will compare the values of the current node and will append a new node with the smaller value. For example, if curr1 has a smaller value than curr2, we will create a new node with the value curr1.val and advance curr1 by using curr1 = curr1.next and vice-versa for curr2.

There may be cases where one list is shorter than the other. We will, first, set default values of variables a and b to Infinity. Then if curr1 is not null, we will update a, and if curr2 is not null we will update b.

To store the new list, we will use a dummy node with the value NaN (the value does not matter, it can be any). A dummy node is a placeholder node that is used to initialise a new linked list when we don't have the head node. In our case, any of the lists can have a smaller head node thus making the head of the new list. For example:

After initializing, the new list dummy is:
NaN
after the first iteration
NaN -> 1
after the second iteration
NaN -> 1 -> 2
after the third iteration
NaN -> 1 -> 2 -> 3
after the third iteration
NaN -> 1 -> 2 -> 3 -> 4
..
..
after the final iteration
NaN -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

So our resulting list starts from the second node of the list starting with dummy i.e. dummy.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 mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode curr1 = l1;
        ListNode curr2 = l2;
    
        ListNode dummy = new ListNode();
        ListNode dummyCurr = dummy;
 
        while(curr1 != null || curr2 != null) {
            int a = Integer.MAX_VALUE;
            int b = Integer.MAX_VALUE;
    
            if (curr1 != null) a = curr1.val;
            if (curr2 != null) b = curr2.val;
        
            if (a < b) {
                ListNode newNode = new ListNode(a);
                dummyCurr.next = newNode;
                dummyCurr = dummyCurr.next;
                curr1 = curr1.next;
            } else {
                ListNode newNode = new ListNode(b);
                dummyCurr.next = newNode;
                dummyCurr = dummyCurr.next;
                curr2 = curr2.next;
            }
        }
    
        return dummy.next;
    }
    
}

m = length first linked list
n = length second linked list
Time complexity- O(m + n)
Space complexity- O(1)

This question concentrates on the developer's knowledge of Java indices and lists.

You are given two singly-linked lists list1 and list2. You are also given two 0-based indices start and end. The two given indices are corresponding to list1. Your task is to remove the nodes between indices start and end of list1 both inclusive and place list2 in place of the deleted nodes.

/*Example*/

Given:
list1 = 11 -> 12 -> 13 -> 14 -> 15 -> 16
list2 = 21 -> 22
start = 2		end = 4
Expected output: 11 -> 12 -> 21 -> 22 -> 16
Explanation:
	list1 = 	11 -> 12 -> 13 -> 14 -> 15 -> 16
	indices =	0	 1	  2	  3	   4	   5
  |		   |
  start	   end (these nodes are deleted)
11 -> 12    13 -> 14 -> 15    16
	    \				  /	
		---> 21 -> 22 --->

Constraint
●	3 <= list1.length
●	1 <= a <= b < list.length - 1
●	1 <= list2.length

Solution:

First, we find the start and the end nodes of list2. These are represented by list2FirstNode and list2LastNode. After that, we find the pointers to nodes at index start - 1 and end + 1. For the given example, to find the node at index start - 1,
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 0
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 1 (we stop here as i == start - 1)

After we get the node at index start - 1, we first store a reference to the next node (node at index start) in temp and then assign it’s next to list2FirstNode. Then we again iterate over list1 to get a reference to the node at index end + 1, and assign next of list2LastNode to this 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 mergeInBetween(ListNode list1, int start, int end, ListNode list2) {
        ListNode list2FirstNode = list2;
        ListNode list2LastNode = list2;
        
        while (list2LastNode.next != null) {
            list2LastNode = list2LastNode.next;
        }
        
        int i = 0;
        ListNode curr = list1;
        
        while(i < start - 1) {
            curr = curr.next;
            i++;
        }
        
        ListNode temp = curr.next;
        curr.next = list2FirstNode;
        
        // curr holds the node at index start
        curr = temp;
        i++;
        
        while(i <= end) {
            curr = curr.next;
            i++;
        }
        
        list2LastNode.next = curr;
        
        return list1;
    }
    
}

m = length second linked list
Time complexity- O(end + m)
Space complexity- O(1)

This interview question shows the developer's ability to work with Java loops.

You are given the head node of a linked list. The linked list is special. In addition to the value of the node and next pointer of the node, the nodes contain additional pointer random. This random pointer points to any random point of the list. It may be null also.

Your task is to create a deep copy of the list. There must be new nodes created corresponding to each node in the given list. Their next and random pointers must point to nodes with the same value as in the given list. None of the pointers in the new list should point to nodes in the given list. Return the head of the new list created.

/*Example*/

Given list
1 -> 2 -> 3 -> 4 -> 5 -> 6
|    |    |    |    |    |
--->-|-->--    |    |    |
     --<----<--|--<--    |
               --->--->---
That is,
1.random = 3
2.random = null
3.random = null
4.random = 6
5.random = 2
6.random = null
Expected output:-
1 -> 2 -> 3 -> 4 -> 5 -> 6
|    |    |    |    |    |
--->-|-->--    |    |    |
     --<----<--|--<--    |
               --->--->---
(We need the exact same list but deep copied.)

Solution:

First, we will create new nodes with values in the original list. For every node in the original list, we will create a new node with the same value and store it in a map reference. The keys of references will be the references of nodes in the original list and the values will be references to corresponding new nodes created. For example,
Let’s say original_{val} be the node in the original list with value val, and new_{val} be the corresponding new node created. After iterating over all the nodes, the map references look like:
{
original_1 -> new_1
original_2 -> new_2
original_3 -> new_3
original_4 -> new_4
original_5 -> new_5
original_6 -> new_6
}

After this, we will again iterate over the original list and will assign corresponding next and random pointers to the new nodes. For one iteration, say curr = original_1, the value of variables in the loop are:
curr = original_1
curr.next = original_2
curr.random = original_3
---------------------------
newNode = new_1
newNode.next = new_2
newNode.random = new_3

// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        
        Node curr = head;
        Map<Node, Node> references = new HashMap<Node, Node>();
    
        while(curr != null) {
            Node newNode = new Node(curr.val);
            references.put(curr, newNode);
            curr = curr.next;
        }
    
        curr = head;
        while(curr != null) {
            Node newNode = references.get(curr);
            newNode.next = references.getOrDefault(curr.next, null);
            newNode.random = references.getOrDefault(curr.random, 
null);
            curr = curr.next;
        }
        
        return references.get(head);
    }

}

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

This question focuses on Java pointers.

You are given the head of a singly linked list. Your task is to check if the list contains a cycle or not.

/*Example*/

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

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

Solution:

This is a very famous problem with a famous solution. The solution is known as fast-slow pointers. We will have two pointers: slow and fast. In every iteration, we will advance slowly by one step while we advance fast by two steps.

● If there is no cycle, the loop will break, as either fast.next or fast.next.next will be null and we will return false.
● If there is a cycle, after the last node, the fast pointer will be in the cycle. It will always be in the cycle. Since the difference of steps between the fast and slow pointer that they take is one only, there will be a point when they both point to the same node. When they do so, we will return true.
For example 2, given list:- 1 -> 2 -> 3 -> 4 -> 5 (5.next = 2 i.e. there is a cycle but we are not showing it here for simplicity)

-> slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (fast pointer is in cycle now, 5.next.next = 2.next = 3)
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (both point to the same node, return true)

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 boolean hasCycle(ListNode head) {
        if (head == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        
            if (slow == fast) return true;
        }
        
        return false;
    }
    
}

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

This interview question shows the developer's ability to work with Java list length.

You are given the head node of a singly linked list. You are also given an integer k. Your task is to rotate the list right by k places.

/*Example*/

Given list: 1 -> 2 -> 3 -> 4 -> 5			k = 2
Expected output: 4 -> 5 -> 1 -> 2 -> 3
Explanation:
After 1st rotation: 5 -> 1 -> 2 -> 3 -> 4
After 2nd rotation: 4 -> 5 -> 1 -> 2 -> 3

Solution:

We first find the length of the list, let it be len. The value of k can be anything, even 0 or greater than len. The list after k rotations and the list after k + len rotations will be the same. So we normalize the value k. We take a modulo of k with len. Now the value lies between 0 and len - 1. If k is 0, then no rotation is required. So we return the head without modifying anything. Otherwise, we iterate over the list. As observed from the example, if the rotations required are 2, 2 nodes from the end of list will become forward. The first (len - k) nodes will be the tail. The (len - k) node (1-indexed) will be the last node in the list after k rotations. Thus we iterate over the list and find the (len - k) node.

The new head of the new list will be (len - k + 1)st i.e. next of (len - k)th. Then iterate up to the last node of the list. After finding the last node, we set it’s next to the original head.

For the given example, len = 5, k = 2
newHead
|
1 -> 2 -> 3 -> 4 -> 5
|
(len - k)th node (this node will be the last node in new list, we set it’s next to null after finding it)

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 rotateRight(ListNode head, int k) {
        if (head == null) return null;
    
        int len = 0;
        ListNode curr = head;
    
        while(curr != null) {
            curr = curr.next;
            len++;
        }
    
        k = k % len;
        if (k == 0) return head;
    
        int i = 1;
        curr = head;
        while(i < (len - k)) {
            curr = curr.next;
            i++;
        }
    
        ListNode newHead = curr.next;
        curr.next = null;
        curr = newHead;
    
        while(curr.next != null) {
            curr = curr.next;
        }
 
        // curr is the last node in the original list
        curr.next = head;
    
        return newHead;
    }
    
}

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