Back to top

Linked List

Quick Video Glance

Overview

In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using queues. We don’t want to overwhelm our readers with a plethora of linked list questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern 1: Using Auxillary Data Structures

Prob 1019: Next Greater Node in Linked List

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /*
     * Question : https://leetcode.com/problems/next-greater-node-in-linked-list/
     *
     * Approach: We use a stack to keep track of the elements encountered so far.
     * Once an element is encountered which is more than the top of the stack, that
     * element gets updated as the next greater element.
     *
     * Time Complexity: O(n)
     * Space Complexity: O(n)
     *
     */
    public class NextGreaterNode {

        public int[] nextLargerNodes(ListNode head) {
            int[] res = new int[getLen(head)];
            Stack<int[]> s = new Stack();
            ListNode curr = head;

            int i = 0;
            while (curr != null) {
                while (!s.isEmpty() && s.peek()[1] < curr.val) {
                    int idx = s.pop()[0];
                    res[idx] = curr.val;
                }
                s.push(new int[]{i, curr.val});
                i++;
                curr = curr.next;
            }
            return res;
        }

        private int getLen(ListNode head) {
            int l = 0;
            ListNode curr = head;
            while (curr != null) {
                l++;
                curr = curr.next;
            }
            return l;
        }
    }

Pattern 2: Sorting Linked List

Prob 148: Sort List

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /*
     * We want to sort the linked list.
     * Question: https://leetcode.com/problems/sort-list/
     *
     * Approach: We sort the linked list using the merge
     * sort technique. We break the list into two halves
     * and then merge them using a recursive approach.
     *
     * Time Complexity: O(nlgn)
     * Space Complexity: O(n)
     *
     */
    public class SortLinkedList {

        ListNode sortList(ListNode node) {
            if (node == null || node.next == null)
                return node;

            ListNode middle = getMiddleNode(node);
            ListNode nextOfMiddle = middle.next;
            middle.next = null;

            ListNode l = sortList(node);
            ListNode r = sortList(nextOfMiddle);
            return mergeList(l, r);
        }

        ListNode mergeList(ListNode l, ListNode r) {
            ListNode result = null;
            if (l == null && r == null) return null;
            if (l == null)
                return r;
            if (r == null)
                return l;

            if (l.val < r.val) {
                result = l;
                result.next = mergeList(l.next, r);
            } else {
                result = r;
                result.next = mergeList(l, r.next);
            }

            return result;
        }

        ListNode getMiddleNode(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

Pattern 3: Two Pointers

Prob 19: Remove Nth Node From End of List

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /*
         * We want to remove the nth node from the end of a list.
         * Question : https://leetcode.com/problems/remove-nth-node-from-end-of-list/
         *
         * Approach: We use the two pointers approach to remove the nth node from the end.
         * One pointer first moves n steps. After that, we move that pointer till we
         * reach end of the list and concurrently move another pointer till it reaches the
         * nth node from end of the list.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode first = head;
            ListNode second = head;

            while (n-- > 0 && second != null) {
                second = second.next;
            }

            // In edge-case, we do need to remove the first node with no previous.
            if (second == null) {
                return head.next;
            }

            // Go till the end, using second pointer
            while (second.next != null) {
                second = second.next;
                first = first.next;
            }

            // First pointer would always be one behind the node to be deleted
            first.next = first.next.next;
            return head;
        }

Prob 141: Linked List Cycle

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /*
         * We need to detect if a cycle exist in a linked list.
         * Question : https://leetcode.com/problems/linked-list-cycle
         *
         * Approach: We use the two pointers approach to find the cycle
         * in a linked list. One pointer moves two nodes at a time and
         * another moves one at a time. If the two pointers coincide then
         * we return true.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public boolean hasCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;

                if (fast == slow) {
                    return true;
                }
            }

            return false;
        }