Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Linked Lists

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Intersection

Given two (singly) linked lists, determine if the two lists intersect. Return the inter-secting node.

Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

You can do this in 0 (A+B) time and 0 (1) additional space. That is, you do not need a hash table (although you could do it with one).

Examples will help you. Draw a picture of intersecting linked lists and two equivalent linked lists (by value) that do not intersect.

Focus first on just identifying if there's an intersection.

Observe that two intersecting linked lists will always have the same last node. Once they intersect, all the nodes after that will be equal.

You can determine if two linked lists intersect by traversing to the end of each and comparing their tails.

Now, you need to find where the linked lists intersect. Suppose the linked lists were the same length. How could you do this?

If the two linked lists were the same length, you could traverse forward in each until you found an element in common. Now, how do you adjust this for lists of different lengths?

Try using the difference between the lengths of the two linked lists.

If you move a pointer in the longer linked list forward by the difference in lengths, you can then apply a similar approach to the scenario when the linked lists are equal.

👊 Solution 1

This is a simple hashmap solutions that is in O(N + M) as we have to traverse both lists, the first time around adding each hashcode of each object to a HashSet. This in order to know if we are referencing the same object.

When we do the checks on the second list, if one of the elements is in the HashSet we can just return the element, else return null.

public static SingleLinkedListNode linkedListIntersectionHashMap(SingleLinkedListNode node1, SingleLinkedListNode node2) {
        HashSet<Integer> hash = new HashSet<>();

        while (node1.next != null) {
            hash.add(node1.hashCode());
            node1 = node1.next;
        }
        
        while (node2.next != null) {
            if (hash.contains(node2.hashCode())) return node2;
            node2 = node2.next;
        }

        return null;
    }

👊 Solution 2

In this approach I could implenent a solution which would require less space and the same runtime O(N+M). I could do this if I can get the length of both lists and move the node which has the longest length by a by the difference between the shortest list and the length of the longest.

if the last node of each list is different we already know the lists have diverged and there is no intersecting node.

From then is just a matter of iterating through the lists until both hashCodes match.

    public static SingleLinkedListNode linkedListIntersectionTailCheck(SingleLinkedListNode node1, SingleLinkedListNode node2) {

        SingleLinkedListNode lastNode1 = getLastNode(node1);
        SingleLinkedListNode lastNode2 = getLastNode(node2);
        if (lastNode1.hashCode() != lastNode2.hashCode()) return null;

        int n1Length = node1.length();
        int n2Length = node2.length();

        if (n1Length > n2Length) {
            for (int i = 0; i < n1Length - n2Length; i++) {
                node1 = node1.next;
            }
        } else {
            for (int i = 0; i < n2Length -  n1Length; i++) {
                node2 = node2.next;
            }
        }

        while (node1.next != null && node2.next != null) {
            if (node1.hashCode() == node2.hashCode()) return node1;
            node1 = node1.next;
            node2 = node2.next;
        }
        return  null;
    }

Question borrowed from “Cracking the coding interview”

Last updated on 3/8/2020
← PalindromeLoop Detection →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
  • 👊 Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr