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

Kth to last node

Implement an algorithm to find the kth to last element of a singly linked list. For example if we have a list with 10 elements and I asked you to return K = 3, the 3rd element from the last should be returned. It is also acceptable to input K = 0, and this would return the last element.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

What if you knew the linked list size? What is the difference between finding the Kth-to- last element and finding the Xth element?

If you don't know the linked list size, can you compute it? How does this impact the runtime?

Try implementing it recursively. If you could find the (K - 1 )th to last element, can you find the Kth element?

You might find it useful to return multiple values. Some languages don't directly support this, but there are workarounds in essentially any language. What are some of those workarounds?

Can you do it iteratively? Imagine if you had two pointers pointing to adjacent nodes, and they were moving at the same speed through the linked list. When one hits the end of the linked list, where will the other be?

👊 Solution 1

Let's try to approach this problem recursively and non recursively. Bear in mind that recursive solutions in this type of scenarios can be written in a cleaner and more concise way (about half the lines of code), but are less optimal in terms of space O(N).

A really easy approach would be if we knew the length of the list, you would just need to find the node at (length - k). So I will not cover this solution.

Let's try to approach this iteratively first. We can have 2 different runners, the first one will move K amount of elements before the second one. In a second loop we can make the first one, and the second one move at the same speed, and once the first one reaches the end the second one will be at Kth position from the end. This solution would be O(N) time and obviously the space required is at a minimum.

public static SingleLinkedListNode kThLastIteratively(SingleLinkedListNode head, int k) {
    SingleLinkedListNode p1 = head;
    SingleLinkedListNode p2 = head;
    for (int i = 0; i < k; i++) {
        if (p1.next == null) return null;
        p1 = p1.next;
    }

    while (p1.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

👊 Solution 2

This algorithm recurses through the linked list. When it hits the end, the method passes back a counter set to 0. Each parent call adds 1 to this counter. When the counter equals k, we know we have reached the kth to last element of the linked list. Implementing this is short and sweet - provided we have a way of "passing back" an integer value through the stack. Unfortunately, we can't pass back a node and a counter using normal return statements in Java. One way to approach this is to change the problem to simply print the kth to last element, then we can pass back the value of the counter simply through return values.

public static int kthLastRecursively(SingleLinkedListNode head, int k) {
    if (head == null) return 0;
    int index = kthLastRecursively(head.next, k) + 1;
    
    if (index == k) System.out.println(k + "th to last node is " + head.data);
    return head.data;
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/6/2020
← Remove duplicatesDelete Middle Node →
  • 👉 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