Ankit Kashyap

Linked List

# Basics

Stats

Neetcode

Easy3
Medium8
Hard3

Structy 15 questions / 24 points points into two parts (17 + 7)

Part 1 (17 = 10 basics + 7 questions)

  • 3 starters: welcome, intro, warm up
  • 4 warm-up questions: values, sum, find, get by index
  • ⭐classic - reverse list
    • Iterative - O(n) time, o(1) space
    • recursive - O(n) space and time
  • ⭐2 classics - zipper lists & merge sorted list
    • Zipper : O(min(n1,n2)) time, O(1) space =just few vars
      • Lengths might be diff. always start from list 1
      • assign tail.next not tail in loops
      • 4 pointers & a counter - current1, current2, head & current/tail .next (new list)
      • Recursion:
    • Merge sorted list
      • Similar to above - but not sure abt the new head
      • Dummy node needed as head might change
      • return dummy.next!
      • Iterative
      • Recursion
  • pep talk
  • 2 easy traversal problems - is universal (unique value linked list) & longest streak

    • is universal

    • longest streak

  • ⭐2 classics - head can change problems - remove node, insert node
    • remove node (only once) - corner scenarios
      • visual
      • if head == target :Head might change but no need of dummy node
      • simply return head.next
      • iterative: break is important for only first deletion case
      • recursion
    • Insert Node : head can change
      • visual
      • index = 0 ⇒ new node becomes head.
  • 2 closers - quiz and wrap up

Part 2 (7 advanced questions)

  • ⭐palindrome - O(n) space and time with a tricky O(n) time + O(1) space
    • Iterative linear solution
    • O(1) solution
      • Use a fast and slow pointer to find the middle.
      • Reverse the second half in-place.
      • Compare both halves. 
        const linkedPalindrome = (head) => {
  if (!head || !head.next) return true;
 
  // Step 1: Find middle (slow will point to middle)
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  // Step 2: Reverse second half
  let prev = null;
  while (slow) {
    let nextNode = slow.next;
    slow.next = prev;
    prev = slow;
    slow = nextNode;
  }
 
  // Step 3: Compare first half and reversed second half
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }
 
  return true;
};
  • ⭐middle value- fast & slow
    • handles odd and even length conditions well out of box
    • in case of even length - it returns the second-mid node
  • ⭐classic - cycle
    • using Set - O(n) space
    • using fast and slow - O(1) space
  • ⭐un-dupe sorted linked list - very good “head may change” prob
    • Dummy node pattern - below code creates a new linked list
    • A better in-place version - O(1) space
  • create linked list - try the recursive o(n) solution
    • simple O(n) dummy node problem
    • Iterative
    • Recursive -using slice - O(N^2)
      • pass index - O(n)
  • build a queue : classic problem - n = number of items currently on the Queue - Total Queue Space: O(n) - enqueue - Time: O(1) - Space: O(1) - dequeue - Time: O(1) - Space: O(1)
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
 
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
 
  enqueue(val) {
    if (this.size === 0) {
      this.head = new Node(val);
      this.tail = this.head;
    } else {
      this.tail.next = new Node(val);
      this.tail = this.tail.next;
    }
    this.size += 1;
  }
 
  dequeue() {
    if (this.size === 0) {
      return null;
    }
    const value = this.head.val;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.size -= 1;
    return value;
  }
}
  • ⭐classic add lists - watch video - https://structy.net/problems/premium/add-lists
    • lots of corner scenarios
      • same length
      • diff length - missing digits as zero
      • handling carry “45 + 46 = 91”
      • handling final carry “45 + 56 = 101”
        • output is longer than each of list
    • o(max(n1, n2)) time and space - we have to parse the longer list completely.
    • iterative:
    • recursive

Problem Checklist

  • Are we changing head? dummy head needed?
  • what we are retruning? Do we need to preserve the head?

Generic Things

  • Insertion - O(1) vs Array’s o(n)
  • Just head is enough to pass on linked list
  • Traversing iterative vs recursive

More patterns

Reversing half of linked list:

  • Use fast = head.next if you want slow to land before midpoint (e.g., to reverse second half).

  • Use fast = head if you want slow to land at or after midpoint (e.g., to reverse first half).

GoalWhere slow should landCorrect fast init
Reverse second halfJust after midpointfast = head.next
Reverse first halfAt or after midpointfast = head
Reorder with middle skipJust before midpointfast = head.next

Reversing second half of linked list - slow and fast start differently

 
function reverseSecondHalf(head) {
  if (!head || !head.next) return head;
 
  // Step 1: Find the middle of the list
  let slow = head, fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  // Step 2: Reverse the second half from 'slow'
  let prev = null, curr = slow;
  while (curr) [curr.next, prev, curr] = [prev, curr, curr.next];
 
  // Step 3: Attach the reversed second half back to the first half
  let mid = head;
  while (mid.next !== slow && mid.next) mid = mid.next;
  mid.next = prev;
 
  return head;
}
  • so 1 → 2 → 3 → 4 → 5
    • Step 1 - find the mid node (slow) as node 3
    • Step 2 - second half becomes like 5 → 4 → 3 where prev is at 5, and slow at 3 → null
      • right now, 2.next is still pointing to 3, and 3.next is now null due to reversal.
    • Step 3 - start again from beginning and come till “2” or where mid.next = slow
    • once there, reconnect 2.next to 5 or mid.next = prev

Reverse the first half - here fast and slow start together

 
function reverseFirstHalf(head) {
  if (!head || !head.next) return head;
 
  // Step 1: Find the middle of the list
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  // Step 2: Reverse the first half from 'head' just befor slow
  let prev = null, curr = head;
  let tail = head; //preserve the head
  while (curr != slow) [curr.next, prev, curr] = [prev, curr, curr.next];
 
  // Step 3: Attach the reversed first half back to the slow
  tail.next = slow;
  return prev;
}
  • Original list: 1 → 2 → 3 → 4 → 5
  • After reversing first half: 2 → 1 → 3 → 4 → 5

Backlinks