LinkedList Common Problems and Solutions

by Sherxon Developer
LinkedList Common Problems and Solutions
This is my second blog on LinkedLists. In this blog, some of the most common problems and their solutions are discussed. You can also read about types of linked lists and implementations in Java in my prvious post, LinkedList Implementation and Basic Operations. To make a best use of this post, please read the question first and do little brainstorm before moving on to the solution. You can also try to implement solution once you are familiar with solution idea.1) Given a singly linked list, determine if it has a cycle in it.

Solution:a) We iterate the list and add each element into the hashtable until current element is null or current element is already in the hashtable. This solution uses O(N) space to store list elements in hashtable. Time complexity is also O(N).b) We can use two pointers: slow and fastslow pointer moves step by step while fast pointer moves two steps at a time. If the linked list has a cycle slow and fast pointers meet at some point. This solution uses O(1) space, which is better than previous solution.Here is implementation of solution in Java.

boolean hasCycle(ListNode head) {
    if(head==null || head.next==null)return false;
    ListNode slow=head;
    ListNode fast=head.next;
    while(slow!=null && fast!=null && fast.next!=null){
        if(slow==fast)return true;
        slow=slow.next;
        fast=fast.next.next;
    }
    return false;
}
2) Given two singly linked lists, find the node at which the intersection of these lists begins. Below given illustration of linked lists with intersection
A:          a1 → a2↘
                    c1 → c2 → c3
                    ↗
B:     b1 → b2 → b3

Solution:

a) The easy solution is adding all elements of the first linked list into Hashset and checking one by one if an element of the second linked list is contained in the hashset.

Time Complexity is O(n+m) and Space Complecity is O(n)b) We iterate both lists and get length of each list. Then move pointer k steps forward on the longer list where k is the difference between lengths of lists. Now we need to move two pointers in both lists starting from head element in shorter list and kth element in longer list. We can find out intersection point the lists when two pointers meet at some point. 

Time Complexity is O(max(m,n)) and Space Complecity is O(1)c) We maintain two pointers x and y at the head of A and B lists respectively. Then we move pointers one node at a time. When x reaches the end of a list, then redirect it to the head of B, similarly when y reaches the end of a list, redirect it the head of A. If at any point x meets y, then x/y is the intersection node.

Time Complexity is O(m+n) and Space Complecity is O(1)Below code snippet shows the third solution.

 ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA==headB) return headA;
    ListNode x=headA;
    ListNode y=headB;
    while (x!=y){
        x= x==null ? headB : x.next;
        y= y==null ? headA : y.next;
    }
    return x;
}


3) Given a linked list, return the node where the cycle begins without modifying the list. If there is no cycle, return null.

Solution: 

a) We iterate the list and add every node into Hashset, if element is already in the set we can return this element as cycle starting point.

Time Complexity is O(n) and Space Complecity is O(n)b) This solution is combination of the first and the second problem solutions. We first find any point in the cycle if there is. Then break the list by setting next pointer of node to null and find intersection point of two lists. The intersection point is the point where cycle begins.

Time Complexity is O(n+m) and Space Complecity is O(1)4) Reverse a singly linked list.

Solution:

a) We can reverse singly linked list in two ways, using recursion and iteration. The idea is to recur until tail node is encountered and set current node as next element of returned element in recursion.

class Solution {
    ListNode newHead;
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        reverse(head);
        head.next = null;
        return newHead;
    }
    ListNode reverse(ListNode current){
        if(current == null || current.next == null) {
            newHead = current;
            return current;
        }
        ListNode prev = reverse(current.next);
        prev.next = current;
        return current;
    }
}
5) Sort a singly linked list in O(n log n) time using constant space complexity.

Solution:

We can use merge sort to sort linked list here. First we need to find mid element of the linked list using two pointers as mentioned above. Then, we should break the link by setting null to the next of mid element. In this case we can have have two lists; left linked list starts from head to mid and right linked list that starts from mid+1 to end of the linked list. We divide linked list until it has only one element in both left and right lists. Then starts merging of left and right lists into one sorted list. You can find solution below in Java

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head;
    ListNode fast = head.next;

    while (fast != null && fast.next != null) { // slow in middle element
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode start2 = slow.next;
    slow.next = null; // break the link

    ListNode start1 = sortList(head); // sort first half
    ListNode start11 = sortList(start2); // sort second half

    return merge(start1, start11); // merge sorted arrays
}

ListNode merge(ListNode a, ListNode b) {
        ListNode root = new ListNode(0); // helper node
        ListNode x = root;
        while (a != null || b != null) {
            if (a == null) {
                x.next = b;
                b = b.next;
            } else if (b == null) {
                x.next = a;
                a = a.next;
            } else if (a.val <= b.val) {
                x.next = a;
                a = a.next;
            } else {
                x.next = b;
                b = b.next;
            }
        x = x.next;
      }
    return root.next;
}

These are some other commonly asked questions in interviews.

April 24, 2019
by Sherxon Developer