linked-lists-problems

1. Linked List cycles

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      return true;
    }
  }
 
  return false;
}

2. Merge two sorted linked lists

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let curr = dummy;
 
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
  }
  curr.next = list1 || list2;
 
  return dummy.next;
}

3. Reverse a linked list

function reverseList(head: ListNode | null): ListNode | null {
  let curr = head;
  let prev = null;
  let next;
 
  while (curr) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
 
  return prev;
}

4. Remove duplicates from a linked list

Skipping a node = change the next of the previous node to the current node’s next

function deleteDuplicates(head: ListNode | null): ListNode | null {
  const visited = new Set();
 
  let prev = null;
  let curr = head;
  while (curr) {
    if (!visited.has(curr.value)) {
      visited.add(curr.value);
      prev = curr;
    } else {
      if (prev) {
        prev.next = curr.next;
      }
    }
    curr = curr.next;
  }
 
  return head;
}

Delete a node in the linked list

function deleteNode(node: ListNode | null): void {
  node.val = node.next.val;
  node.next = node.next.next;
}

Intersection of two lists

Let the tracking nodes a and b to go through the same amounts of nodes. So, when they are equal, they have gone through the same amount of nodes, hecne teh intersection.

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null,
): ListNode | null {
  let a = headA;
  let b = headB;
 
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
 
  return a;
}

Remove elements

function removeElements(head: ListNode | null, val: number): ListNode | null {
  let dummy = new ListNode(0, head);
  let curr = dummy;
 
  // curr.next - what we check, and curr is the previous one
  // instead of using a prev value
  while (curr.next) {
    if (curr.next.val === val) {
      curr.next = curr.next?.next;
    } else {
      curr = curr.next;
    }
  }
 
  return dummy.next;
}