Home/Blog/Interview Prep/Top linked list interview questions and answers

Top linked list interview questions and answers

18 min read

Feb 22, 2024

content

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

A linked list is a linear data structure consisting of connected nodes placed in a non-contiguous manner in the memory. Each node typically consists of an associated value and a pointer to the next node.

Linked lists are crucial in solving quite a lot of problems, and they constitute a major part of interviews containing data structures. The following blog covers diverse questions on linked lists, including the problem statement, the intuition behind solving the problem, the code and a detailed explanation following the code. We also discuss the time and space complexity for each solution to assess the efficiency. The diversity of questions will equip you to be prepared for many similar questions, and by the end of this blog, you will learn algorithms like the Hare and Tortoise algorithm to solve linked list problems efficiently.

1. How to reverse a linked list#

Problem statement#

The problem at hand is to reverse a linked list in-place, i.e., to change the direction of the links between nodes so that the last node becomes the first node, the second-to-last node becomes the second node, and so on.

Intuition#

A linked list can be reversed by applying various methods, such as using a data structure (e.g., a stack), using recursion, or through an iterative process. We’ll be using an iterative approach to reverse a linked list because such an approach doesn’t require extra auxiliary space. The intuition behind the iterative approach will be to change the next pointers of each node to start pointing to the previous node instead.

public class List {
    static Node headPtr;
    static class Node {
        
        int value;
        Node nextPtr;
        Node(int value) {
            this.value = value;
            this.nextPtr = null;
        }
    }
    void insertAtEnd(int value) {
        
        Node newNode = new Node(value);
        if (headPtr == null) {
            headPtr = newNode;
            return;
        }
        Node lastNode = headPtr;
        
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = newNode;
    }
    void reverse(){
        
        Node prev = null;
        Node curr = headPtr;
        Node next = null;
        
        while(curr != null){
            next = curr.nextPtr;
            curr.nextPtr = prev;
            prev = curr;
            curr = next;
        }
        headPtr = prev;
    }
    
    void print(){
        
        for(Node curr = headPtr; curr != null; curr = curr.nextPtr){
            System.out.print(curr.value + " ");
        }
        System.out.println("");
    }
    public static void main(String [] args){
        
        List myList = new List();
        
        myList.insertAtEnd(1);
        myList.insertAtEnd(2);
        myList.insertAtEnd(3);
        myList.insertAtEnd(4);
        myList.insertAtEnd(5);
        myList.insertAtEnd(6);
        myList.insertAtEnd(7);
        
        System.out.print("Original list: ");
        myList.print();
        
        myList.reverse();
        
        System.out.print("Reversed list: ");
        myList.print();
    }
}

Code explanation#

A node curr is defined to keep track of the current node. It’s initially set to headPtr because the iteration starts from the head pointer.
A node prev is defined to keep track of the current node’s previous node. It is initially set to null because there’s no previous node for the head pointer (headPtr).
A node next is defined to keep track of the node directly after the current node. It’s initially set to null and will be updated within the loop.
A while loop first ensures whether the current node exists. In case it does, the following assignments are made:
- The next node is updated to store the pointer after the current node by accessing it through current.nextPtr.
- To reverse the linked list, the pointer pointing toward the next node of the current node is made to point to the previous node of the current node. This simply reverses the direction of the links between the nodes one by one.
- The prev node is now made to point to the current node for the next iteration.
- The curr node is updated to point to the next node of the current node, stored in next, for the next iteration.
Once the list is completely traversed, the head node headPtr is updated to the updated current value, i.e., the last node after the complete traversal. The list is now completely reversed, and headPtr is pointing to the last node.

Time and space complexity#

The linked list is traversed only once while changing the direction of the next pointers of each node, resulting in a time complexity of $O(n)$ Because no extra auxiliary space is used, the space complexity turns out to be $O(1)$ only.

2. Finding the middle of a linked list#

Problem statement#

The problem at hand is to find the middle node of a linked list. If the length of the linked list is odd, there is only one middle node. Otherwise, there are two middle nodes, and either of them can be returned.

Intuition#

One approach could be to make two traversals, one for counting the length $n$ of the linked list and the other for iterating through $n/2$ nodes (half the length). An efficient way is to use the Hare and Tortoise algorithm. Two pointers are employed, and one moves twice as fast as the other. The middle is obtained when the fast pointer reaches the end and the slow pointer reaches the middle.

public class MiddleOfTheList {
    static Node headPtr;
    static class Node {
        
        int value;
        Node nextPtr;
        Node(int value) {
            this.value = value;
            this.nextPtr = null;
        }
    }
    void insertAtEnd(int value) {
        
        Node newNode = new Node(value);
        if (headPtr == null) {
            headPtr = newNode;
            return;
        }
        Node lastNode = headPtr;
        
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = newNode;
    }
    Node findMiddle(){
        
        if(headPtr == null){
            return null;
        }
        
        if(headPtr.nextPtr == null){
            return headPtr;
        }
        
        // we can also return headPtr.next here
        if(headPtr.nextPtr.nextPtr == null){
            return headPtr; 
        }
        
        Node slowPtr = headPtr;
        Node fastPtr = headPtr;
        
        while (fastPtr.nextPtr != null && fastPtr.nextPtr.nextPtr != null) {
            fastPtr = fastPtr.nextPtr.nextPtr;
            slowPtr = slowPtr.nextPtr;
        }
        
        return slowPtr;
    }
    
    void print(){
        
        for(Node current = headPtr; current != null; current = current.nextPtr){
            System.out.print(current.value + " ");
        }
        System.out.println("");
    }
    public static void main(String [] args){
        
        MiddleOfTheList myList = new MiddleOfTheList();
        
        myList.insertAtEnd(7);
        myList.insertAtEnd(9);
        myList.insertAtEnd(11);
        myList.insertAtEnd(13);
        myList.insertAtEnd(15);
        myList.insertAtEnd(17);
        myList.insertAtEnd(19);
        
        Node middle = myList.findMiddle();
        
        if(middle != null){
            System.out.print("The middle node is " + middle.value);
        }else{
            System.out.print("Empty linked list!");
        }
    }
}

Code explanation#

The findMiddle() method returns null if no middle pointer is found, i.e., the list is empty.
If there’s only one element, i.e., the headPtr node, it’s returned as the middle element.
If there are two elements in the list, the headPtr and the headPtr.nextPtr nodes, any node can be returned as the middle element. Here, we return the headPtr node.
For multiple elements, two pointers, slowPtr and fastPtr, are initialized to the headPtr node. The slowPtr pointer traverses each node one by one, while the fastPtr pointer skips one node each time.
By the time the fastPtr pointer reaches the end of the linked list, the slowPtr pointer has reached the middle of the list, therefore obtaining the middle value.

This node is then returned by the findMiddle() method.

Time and space complexity#

Because we’re traversing the entire list linearly, the time complexity is $O(n)$ . The space complexity is $O(1)$ because no extra space is utilized except for a constant number of pointers.

3. Removing duplicates in a sorted linked list#

Problem statement#

The task at hand is to remove duplicates from a sorted linked list. Removing duplicates means that we have to eliminate nodes with duplicate values. This leaves only distinct values in the linked list.

Intuition#

We know that the linked list is sorted, so the duplicates will occur consecutively. To remove duplicates, we can simply iterate through the list, comparing each node’s value with the next one. If two consecutive nodes are equal, we then update the next pointer of the current node to skip the duplicate node.

public class SortedList {
    static Node headPtr;
    static class Node {
        
        int value;
        Node nextPtr;
        Node(int value) {
            this.value = value;
            this.nextPtr = null;
        }
    }
    void insertAtEnd(int value) {
        
        Node newNode = new Node(value);
        if (headPtr == null) {
            headPtr = newNode;
            return;
        }
        Node lastNode = headPtr;
        
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = newNode;
    }
    void removeDuplicates(){
        
        Node current = headPtr;
        
        while (current != null && current.nextPtr != null) {
            if (current.value == current.nextPtr.value) {
                current.nextPtr = current.nextPtr.nextPtr;
            } else {
                current = current.nextPtr;
            }
        }
    }
    
    void print(){
        
        for(Node current = headPtr; current != null; current = current.nextPtr){
            System.out.print(current.value + " ");
        }
        System.out.println("");
    }
    public static void main(String [] args){
        
        SortedList sortedList = new SortedList();
        
        sortedList.insertAtEnd(1);
        sortedList.insertAtEnd(2);
        sortedList.insertAtEnd(2);
        sortedList.insertAtEnd(3);
        sortedList.insertAtEnd(4);
        sortedList.insertAtEnd(4);
        sortedList.insertAtEnd(4);
        sortedList.insertAtEnd(5);
        
        System.out.print("Original sorted list: ");
        sortedList.print();
        
        sortedList.removeDuplicates();
        
        System.out.print("List after removing duplicates: ");
        sortedList.print();
    }
}

Code explanation#

A pointer named current is used to traverse the linked list.
The while loop ensures that the end of the list is not reached.
Within the loop, it’s checked if a duplicate is found or not. If the current node’s value is equal to the value of its next node, the next pointer of the current node is updated to skip the duplicate node.
If no duplicate is found, the current pointer is moved to the next node to check with the further nodes.
The process continues until the end of the list is reached.

Time and space complexity#

Because we’re traversing the entire list only once, the time complexity is $O(n)$ . The space complexity is only $O(1)$ because no extra space is utilized except for a constant number of pointers.

4. Detecting a loop in a linked list#

Problem statement#

The challenge is to identify the presence of a loop in a linked list. A loop occurs when a node in the list points to a node present earlier in the list, forming a cycle within the linked structure.

Intuition#

To detect a loop, we can use Floyd’s Tortoise and Hare algorithm, a very crucial algorithm when it comes to linked lists. It involves two pointers moving through the list at different speeds. If there’s a loop, the two pointers will meet one way or another. The slow pointer advances one node at a time, and at the same time, the fast pointer advances two nodes at a time.

Code#

Let’s delve into the implementation of this solution.

public class LoopDetection {
    static Node headPtr;
    static class Node {
        
        int value;
        Node nextPtr;
        Node(int value) {
            this.value = value;
            this.nextPtr = null;
        }
    }
    void insertAtEnd(int value) {
        
        Node newNode = new Node(value);
        if (headPtr == null) {
            headPtr = newNode;
            return;
        }
        Node lastNode = headPtr;
        
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = newNode;
    }
    boolean detectLoop() {
        
        Node tortoise = headPtr;
        Node hare = headPtr;
        
        while (hare != null && hare.nextPtr != null) {
            tortoise = tortoise.nextPtr;
            hare = hare.nextPtr.nextPtr;
            if (tortoise == hare) {
                return true;             
            }
        }
        
        return false;
    }
    public static void main(String [] args){
        
        LoopDetection loopDetection = new LoopDetection();
        
        loopDetection.insertAtEnd(1);
        loopDetection.insertAtEnd(2);
        loopDetection.insertAtEnd(3);
        loopDetection.insertAtEnd(4);
        loopDetection.insertAtEnd(5);
        
        // we add a loop deliberately for demonstration purposes
        headPtr.nextPtr.nextPtr.nextPtr.nextPtr.nextPtr = headPtr.nextPtr.nextPtr;
        
        boolean hasAnyLoop = loopDetection.detectLoop();
        
        if (hasAnyLoop) {
            System.out.println("The linked list has a loop!");
        } else {
            System.out.println("No loop in the linked list!");
        }
    }
}

Code explanation#

Two pointers, tortoise and hare, are both initialized to the head of the linked list.
The while loop continues until the hare node reaches the end of the list or a loop is detected.
The while loop ensures that the hare pointer points to a valid node and, if it does, also ensures that the next node for the hare pointer exists. These two checks remove the chances of accessing an empty node in case the linked list was completely traversed in the previous iteration (therefore removing any chances of error).
In each iteration, the tortoise node moves one step, and the hare node moves two steps. We do this by assigning the next pointer of the tortoise node to the tortoise node and the next-to-next pointer of the hare node to the hare node.
If there’s a loop, the two pointers will meet at some point within the loop.
If no loop is present, the hare node will reach the end of the list, and the loop detection process will simply end.

Time and space complexity#

The time complexity for the above code is $O(n)$ , where $n$ is the number of nodes in the linked list. The space complexity is only $O(1)$ because we’re only traversing the current linked list.

5. Converting a singly linked list into a circular linked list#

Problem statement#

The objective here is to convert a singly linked list into a circular linked list. Let’s understand a circular linked list first. In a circular linked list, the last node’s next pointer is not null but points back to the head of the list, forming a loop.

Intuition#

To convert a singly linked list into a circular one, we can simply set the next pointer of the last node to point back to the head of the list.

public class SinglyToCircular {
    static Node headPtr;
    static class Node {
        
        int value;
        Node nextPtr;
        Node(int value) {
            this.value = value;
            this.nextPtr = null;
        }
    }
    void insertAtEnd(int value) {
        
        Node newNode = new Node(value);
        if (headPtr == null) {
            headPtr = newNode;
            return;
        }
        Node lastNode = headPtr;
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = newNode;
    }
    void convertToCircular() {
        
        if (headPtr == null) {
            return; 
        }
        Node lastNode = headPtr;
    
        while (lastNode.nextPtr != null) {
            lastNode = lastNode.nextPtr;
        }
        lastNode.nextPtr = headPtr;
    }
    public static void main(String [] args){
        
        SinglyToCircular conversion = new SinglyToCircular();
        
        conversion.insertAtEnd(1);
        conversion.insertAtEnd(2);
        conversion.insertAtEnd(3);
        conversion.insertAtEnd(4);
        conversion.insertAtEnd(5);
        
        System.out.print("Original singly linked list: ");
        conversion.print();
        conversion.convertToCircular();
        System.out.print("Circular linked list: "); 
        conversion.print();
    }
    void print(){
        
        Node current = headPtr;
        
        do {
            System.out.print(current.value + " ");
            current = current.nextPtr;
        } while (current != null && current != headPtr);
        
        System.out.println("");
    }
}

Code explanation#

The convertToCircular() method first makes the necessary checks, i.e., if the linked list is empty. If it is, the function simply returns.
The method is used to reach the last node within the linked list. This is achieved by moving through the list until the next pointer is null.
Once the last node is found, the next pointer of this node is updated to point back to the head of the list. This effectively makes a circular structure.
The print() method is modified to accommodate circular linked lists. It uses a do-while loop to print the values of the nodes until it returns to the head, ensuring all nodes in the circular list are displayed and the process doesn’t go on infinitely.

Time and space complexity#

The time complexity is $O(n)$ , where $n$ is the number of nodes in the linked list because we traverse the list only once. The space complexity is $O(1)$ because only a constant number of pointers are used.

6. Inserting values in a sorted way in a doubly linked list DLL#

Problem statement#

The task at hand is to insert a value in sorted order within a doubly linked list. The doubly linked list is sorted in ascending order, and the important part is to maintain this ordering after the insertion.

Intuition#

To insert a value in sorted order, we can traverse the doubly linked list until we find the correct position for the new value. Once the position is identified, we create a new node and update its next and previous pointers to integrate it into the list.

Code#

Let’s delve into the implementation of this solution.

public class SortedInsert {
    static Node head;
    static Node tail;
    static class Node {
        int data;
        Node prev;
        Node next;
        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
    void insertSorted(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        if (value < head.data) {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
            return;
        }
        if (value > tail.data) {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
            return;
        }
        Node current = head;
        while (current != null && value > current.data) {
            current = current.next;
        }
        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;
    }
    void print() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        SortedInsert sortedInsert = new SortedInsert();
        sortedInsert.insertSorted(3);
        sortedInsert.insertSorted(7);
        sortedInsert.insertSorted(5);
        sortedInsert.insertSorted(9);
        System.out.print("Sorted doubly linked list: ");
        sortedInsert.print();
    }
}

Code explanation#

The insertSorted() method, first and foremost, creates a new node with the given value.
If the list is empty, the new node becomes both the head and the tail.
If the value is less than the head pointer’s data, i.e., the new node should be the first value, and the new node is inserted at the beginning.
If the value is greater than the tail pointer’s data, i.e., the new node should be the last, and the new node is inserted at the end.
If none of the above conditions fit, the method begins to traverse the list to find the correct position for the new value. Once it’s found, the next and previous pointers of the neighboring nodes are updated to integrate the new node into the sorted list. The following points break down the details:
- newNode.prev: Sets the prev pointer of the new node to the prev pointer of the current node
- newNode.next: Sets the next pointer of the new node to the current node
- current.prev.next: Updates the next pointer of the node before the current node to point to the new node
- current.prev: Updates the prev pointer of the current node to point to the new node

Time and space complexity#

The time complexity is $O(n)$ , where $n$ is the number of nodes in the doubly linked list. The space complexity is $O(1)$ because, like most of the questions, only a constant number of pointers are used.

7. Finding the intersection point of two linked lists#

Problem statement#

The challenge here is to determine the intersection point of two linked lists. Let’s first understand what an intersection point is before moving on. An intersection point is simply a node at which both linked lists converge, arriving at the same (common) node.

Intuition#

To find the intersection point, we can first calculate the lengths of both linked lists. Then, we align the starting points of the lists by changing the starting position of the longer list. Once the distance from both of the starting points of the lists to the common node is the same, we iterate through both lists and compare nodes until we find the intersection point.

Code#

Let’s delve into the implementation of this solution.

public class IntersectionPoint {
    static Node head1;
    static Node head2;
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    int findLength(Node head) {
        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }
    Node getIntersectionNode(Node headA, Node headB) {
        int lengthA = findLength(headA);
        int lengthB = findLength(headB);
        Node currentA = headA;
        Node currentB = headB;
        while (lengthA > lengthB) {
            currentA = currentA.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            currentB = currentB.next;
            lengthB--;
        }
        while (currentA != null && currentB != null) {
            if (currentA == currentB) {
                return currentA;
            }
            currentA = currentA.next;
            currentB = currentB.next;
        }
        return null; 
    }
    public static void main(String[] args) {
        IntersectionPoint intersectionFinder = new IntersectionPoint();
        Node intersectionNode = new Node(7);
       
        head1 = new Node(3);
        head1.next = new Node(1);
        head1.next.next = new Node(5);
        head1.next.next.next = new Node(9);
        head1.next.next.next.next = intersectionNode;
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(1);
       
        head2 = new Node(4);
        head2.next = new Node(6);
        head2.next.next = intersectionNode;
        Node intersection = intersectionFinder.getIntersectionNode(head1, head2);
        if (intersection != null) {
            System.out.println("Intersection point: " + intersection.data);
        } else {
            System.out.println("No intersection point between lists!");
        }
    }
}

Code explanation

The findLength() method is responsible for calculating the length of a linked list. It traverses the list and uses a counter length to increase it for each node traversed.
The getIntersectionNode() method first finds the lengths of both linked lists using the findLength() method.
It then adjusts the starting positions of the lists so that they both have the same number of nodes left till the intersection point. This ensures that when we iterate through both lists, we reach the intersection point at the same time.
The iteration through the adjusted lists continues until either an intersection point is found (common node) or the end of one of the lists is reached.
If an intersection point is found, the common node is returned. Otherwise, null is returned.

Time and space complexity#

The time complexity is $O(m + n)$ , where $m$ and $n$ are the lengths of the two linked lists. The space complexity is $O(1)$ since only a constant number of pointers are used.

8. Modify the values of the first half nodes in a singly linked list without using extra space#

Problem statement#

Given a singly linked list containing $n$ nodes, the task is to modify the values of the first half nodes so that the new value for the $i$ -th node in the first half is equal to the difference between the value of the corresponding node from the second half of the linked list and the current value of the $i$ -th node. If the number of nodes, $n$ , is odd, the value of the middle node remains unchanged. Most importantly, the memory complexity should be $O(1)$ .

Intuition#

To solve this problem while using $O(1)$ extra memory, we can use a two-pointer approach. The slow pointer will traverse the linked list, and the fast pointer will help identify the middle of the list. We’ll reverse the second half of the list, modify the values of the first half based on the conditions, reverse the second half again to restore the starting order, and lastly, we’ll connect the reversed second half back to the original list.

public class ModifyFirstHalf {
    static Node head;
    static class Node {
        int value;
        Node next;
        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }
    void modifyValues() {
        if (head == null || head.next == null) {
            return;
        }
        Node slowPtr = head;
        Node fastPtr = head;
        Node prev = null;
        while (fastPtr != null && fastPtr.next != null) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
        prev = slowPtr.next;
        slowPtr.next = null;
        Node secondHalf = reverse(prev);
        prev = secondHalf;
        Node firstHalf = head;
        while (firstHalf != null && secondHalf != null) {
            firstHalf.value = secondHalf.value - firstHalf.value;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
            
        }
        prev = reverse(prev);
        if (prev != null) {
           slowPtr.next = prev;
        }
    }
    Node reverse(Node start) {
        Node prev = null;
        Node current = start;
        Node next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
          
        }
        return prev;
    }
    void insertAtEnd(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
    }
    void print() {
        for (Node current = head; current != null; current = current.next) {
            System.out.print(current.value + " ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        ModifyFirstHalf list = new ModifyFirstHalf();
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        list.insertAtEnd(4);
        list.insertAtEnd(5);
        System.out.print("Original list: ");
        list.print();
        list.modifyValues();
        System.out.print("Formula list: ");
        list.print();
    }
}

Code explanation#

Two pointers, slowPtr and fastPtr, are used to traverse the linked list. The fastPtr pointer moves twice as fast as the slowPtr pointer (it makes two jumps each time). When fastPtr reaches the end of the list, slowPtr reaches the middle.
During this traversal, a prev pointer keeps track of the node before the slowPtr node.
The second half of the list (starting from slowPtr) is reversed using the reverse() function.
The reversed second half is stored in the secondHalf node.
The pointers firstHalf and secondHalf traverse the first half and the reversed second half simultaneously.
Values of the first half nodes are modified by subtracting the current values from the corresponding values in the reversed second half.
The reversed second half is reversed again through the reverse() function to restore it to the original order.
The reversed second half is connected back to the original list.

Time and space complexity

Traversing the list to find the middle and reverse the second half takes $O(n/2)$ time. Modifying values, reversing the second half again, and connecting the modified list also take $O(n/2)$ time. Therefore, the final time complexity is $O(n)$ with $O(1)$ space complexity because no additional memory is used except for a constant number of pointers.

9. Merge kkk sorted linked lists#

Problem statement

Given an array of $k$ linked lists, where we have each linked list sorted in ascending order, the task is to merge all the linked lists into one sorted linked list and return the final merged result. The input is an array of linked lists, and the output is a single linked list, which is also sorted.

Intuition#

To efficiently merge $k$ sorted linked lists, a priority queue (min-heap) can be employed. The priority queue helps maintain the smallest element among the heads of all linked lists. This ensures that the next element to be added to the merged list is always the smallest available.

import java.util.PriorityQueue;
public class MergeKSortedLists {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }
    ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            current.next = minNode;
            current = current.next;
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        MergeKSortedLists merger = new MergeKSortedLists();
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);
        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);
        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);
        ListNode[] allLinkedLists = {list1, list2, list3};
        ListNode result = merger.mergeKLists(allLinkedLists);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Code explanation#

A method named mergeKLists() created to perform the merge. If the list is empty, the method simply returns.
A priority queue named minHeap is created, and the elements added to it are ListNode objects. The comparator used for ordering is implemented by the lambda expression (a, b) -> a.val - b.val, which ensures that the priority queue is a min-heap.
Each linked list from the lists is iterated, and in case it is not empty, its head node is added to the min heap.
The code initializes a dummy node and a current node to keep track of the merged list. It then repeatedly extracts the minimum node from the min heap using the minHeap.poll() method and appends it to the merged list by updating current node’s next pointer with the minNode pointer. If the extracted node has a next node, it is added back to the min heap through the minHeap.offer(minNode.next) method call.
At last, the method returns the merged sorted linked list and excludes the dummy node.

Time and space complexity#

The time complexity of this algorithm is $O(N \log k)$ , where $N$ is the total number of nodes in all linked lists, and $k$ is the total number of linked lists. The space complexity is $O(k)$ because here, we’re using extra space in the form of a priority queue.

10. Add two numbers represented using linked lists#

Problem statement#

Given two non-empty linked lists representing two nonnegative integers, where each node contains a single digit, our task here is to add the two numbers and return the sum as a linked list.

The digits are stored in reverse order, and each of their nodes contains a single digit. We add the two numbers and return the sum as a linked list.

Intuition#

We can traverse both linked lists simultaneously, adding corresponding digits. We also need to add the carry (if any) for each sum we make. We can create a new node for each sum digit and keep track of the carry for the next iteration. It’s very important to handle cases where one linked list is longer than the other or where there is a final carry.

public class AddTwoNumbers {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }
    ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        
        AddTwoNumbers addingVals = new AddTwoNumbers();
        ListNode num1 = new ListNode(2);
        num1.next = new ListNode(4);
        num1.next.next = new ListNode(3);
        ListNode num2 = new ListNode(5);
        num2.next = new ListNode(6);
        num2.next.next = new ListNode(4);
         
        ListNode result = addingVals.addTwoNumbers(num1, num2);
     
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Code explanation#

A dummy named node is created to act as the dummy head of our final sum linked list.
A pointer named current is initialized to point to the dummy node. This pointer is used to traverse and build the new linked list.
A variable carry is initialized to 0. It will store the carry generated during the addition of digits (if any).
A while loop is used to iterate through the linked lists l1 and l2.
Inside the loop, the values of the current nodes in l1 and l2 are extracted or set to 0 if any value is null.
The sum of the digits, along with the carry from the previous step, is calculated.
The carry for the next iteration is updated based on the sum divided by 10.
A new node is created in the result list, with the value being the remainder of the sum when divided by 10. This step ensures that only the last digit is added to the result list.
The current pointer is moved to the next node in the result list.
The pointers l1 and l2 are moved to their respective next nodes.
After the loop, a check is made to see if there’s any remaining carry. If there is, a new node is added to the result list with the carry.
The function returns the next node of the dummy head, which represents the actual head of the result list.

Note: The answer obtained has its digits reversed.

Time and space complexity#

The time complexity for this question is $O(max(N, M))$ , where $N$ and $M$ will be the lengths of the lists to be added, respectively. The space complexity is $O(max(N, M))$ because the added value will have a length equal to the greater length of the two list lengths.

Written By:

izza ahmad

Join 2.5 million developers at

Explore the catalog

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments