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

Palindrome

Implement a function to check if a linked list is a palindrome.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

A palindrome is something which is the same when written forwards and backwards. What if you reversed the linked list?

Try using a stack.

Assume you have the length of the linked list. Can you implement this recursively?

👊 Solution 1

As we know a palindrome is just the same frontwards and backwards, one easy to implement approach would be to reverse the list values and compare them. This is a nice implementation as we can break down each step onto a separate function. The runtime would be of O(N).

    public static boolean linkedListPalindromeReverseAndCompare(SingleLinkedListNode node) {
           SingleLinkedListNode reversed = reverseList(node);
            return compareLists(node, reversed);
    }

    private static boolean compareLists(SingleLinkedListNode n1, SingleLinkedListNode n2) {
        while (n1 != null) {
            if (n1.data != n2.data) return false;
            n1 = n1.next;
            n2 = n2.next;
        }
        return true;
    }

👊 Solution 2

One approach to do this is to use a stack to keep track of the elements in the linked list up to the halfway point. We ignore the middle node if the list has an odd length. Then we start popping from the stack after the halfway point and see if the node values are same until we reach the end of the list.

The tricky part is to find the half way point. In a singly linked list, we cannot easily access it's length without traversing the whole list and we also can't traverse backwards. This is where the runner technique would be really useful. There are two cases we have to handle (odd or even length list). The following visualization explains the runner technique in action.

Odd length list

12345
SSS
FFF

Even length list

123456NULL
SSSS
FFFF

As you can see, if we use the runner technique the slow pointer will always end up in the middle of the list. The only issue here is when the list is odd in length which we simply just ignore the middle node by pointing the slow pointer to it's next node. We know that the list is odd in length if the fast pointer is not null (as shown in the visualization above).

public boolean isPalindrome(Node head) {
  if (head.next == null) return false;

  Node slow = head;
  Node fast = head;
  Stack<Integer> stack = new Stack<>();

  while (fast != null && fast.next != null) {
    stack.push(slow.data);
    slow = slow.next;
    fast = fast.next.next;
  }

  // When list had odd length, simply ignore the middle node
  if (fast != null) slow = slow.next;

  while (slow != null) {
    if (stack.pop() != slow.data) return false;
    slow = slow.next;
  }

  return true;
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/8/2020
← Sum ListIntersection →
  • 👉 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