Interview Cheat Sheets | Linked List Cheat Sheet

December 26th, 2023

Introduction

This article will serve to further summarize the excellent overview of linked lists from the tech interview handbook.

Overview

• Linked lists represent sequential data, consisting of nodes with data and references to the next node.
• Unlike arrays, the order is not determined by memory placement.

Advantages

• O(1) insertion and deletion of a node at a given location.

Disadvantages

• O(n) access time, as direct access by position is not possible.

Types of Linked Lists

• Singly-linked list: Each node points to the next, and the last node points to null.
• Doubly linked list: Each node has the next and `prev“ pointers.
• Circular linked list: The last node points back to the first node.

Time Complexity

Common Routines

• Counting the number of nodes
• Reversing a linked list in place
• Finding the middle of a linked list using two pointers (fast and slow) - My solution
• Merging two linked lists together

Corner Cases

• Empty list

• Single node

• Two nodes

• Cycles in a linked list

  Tip: Clarify beforehand with the interviewer whether there can be a cycle in the list. Usually, the answer is no and you don't have to handle it in the code

Techniques

• Sentinel/dummy nodes for edge cases

  • The dummy node technique involves adding a placeholder node (also called a dummy node or sentinel node) at the beginning and/or end of a linked list to simplify edge cases and avoid special conditional checks. Here’s an explanation of how it works and its benefits:

  1. Adding a Dummy Node at the Head:

     • Placing a dummy node at the beginning of the linked list helps handle scenarios where operations need to be performed at the head.
     • It ensures that the head itself is never a special case, making the implementation of various algorithms cleaner.
     • This technique eliminates the need for separate code to handle an empty list or operations specifically on the first node.

  2. Adding a Dummy Node at the Tail:

     • Similarly, adding a dummy node at the end simplifies operations involving the tail of the linked list.
     • It ensures that the last node is never a special case, making the code more consistent and easier to understand.
     • It eliminates the need for additional checks to see if the current node is the last one.

  3. Removing the Dummy Node:

     • After performing operations, it’s essential to remove the dummy node if added temporarily.
     • This step ensures that the dummy node doesn’t affect the results or interfere with subsequent operations.
     • Removal is typically done after the main logic, making it a clean and predictable process.

  4. Benefits:

     • Simplifies edge cases: With a dummy node, you don’t need separate logic for an empty list or special conditions at the head or tail.
     • Cleaner code: The presence of dummy nodes allows you to treat all nodes uniformly, leading to cleaner and more readable code.
     • Consistent operations: By avoiding special cases, the code becomes more consistent, reducing the likelihood of errors.

• Two pointers for various problems

  • Getting the kth from the last node - Have two pointers, where one is k nodes ahead of the other. When the node ahead reaches the end, the other node is k nodes behind
  • Detecting cycles - Have two pointers, where one pointer increments twice as much as the other, if the two pointers meet, means that there is a cycle
  • Getting the middle node - Have two pointers, where one pointer increments twice as much as the other. When the faster node reaches the end of the list, the slower node will be in the middle

Using Space

• Consider in-place modification without additional storage.

Elegant Modification Operations

• Truncate a list - Set the next pointer to null at the last element
• Swapping values of nodes - Just like arrays, just swap the value of the two nodes, there’s no need to swap the next pointer
• Combining two lists - attach the head of the second list to the tail of the first list

Essential Questions

• Reverse a Linked List - My solution
• Detect Cycle in a Linked List - My solution

Recommended Practice Questions

• Merge Two Sorted Lists - My solution
• Merge K-Sorted Lists
• Remove Nth Node From End Of List
• Reorder List