108 Remove N-th Node From End (Two pointers to remove target node)

 

Approach: Two-Pointer (Normal, 2-pass method)

     Idea:

1. First, traverse the entire list to find the length.

2. Then, calculate the (length - n) position from the start.

3. Traverse again to the (length - n - 1)-th node (the node before the one to delete).

4. Delete the N-th node from the end.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head

    # Step 1: Find the length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Step 2: Find (length - n)-th node
    current = dummy
    for _ in range(length - n):
        current = current.next

    # Step 3: Delete the node
    current.next = current.next.next

    return dummy.next

105 Linked List Cycle Detect if a cycle exists

 

Problem Statement

Given: The head of a singly linked list.
Goal: Determine whether there is a cycle in the list.

 What is a cycle?

A cycle exists when a node's next pointer refers back to a previous node instead of None.

Approach: Fast and Slow Pointers (Floyd's Algorithm)

Idea:

Use two pointers:

• Slow pointer moves one step at a time.

• Fast pointer moves two steps at a time.

If there is a cycle, the fast pointer will eventually meet the slow pointer.

If there is no cycle, the fast pointer will reach the end (None).

Why it works:

In a cycle, the fast pointer laps around the cycle and will eventually “catch” the slow pointer, similar to two runners on a circular track.

Time	O(n)	In worst case, fast traverses the list once
Space	O(1)	No extra space used

def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps

        if slow == fast:
            return True           # cycle detected

    return False                  # no cycle

Why "eventually"?

Because:

• They do not meet immediately.

• The fast pointer is moving 2 steps at a time, slow is moving 1 step at a time.

• The distance between them changes over time, and they gradually close the gap.

• It may take multiple iterations before they land on the same node.

103 Delete Node in a Linked List

Delete Node in a Linked List Delete

Problem Summary

You are given only a reference to a node (not the head) in a singly linked list. The node is not the tail.
You need to delete this node from the list.

What You Cannot Do

• You cannot traverse from the head to find the previous node.

• You do not have access to the previous node, so you can't modify its next pointer.

---

What You Can Do (The Trick )

You copy the value of the next node into the current node, and then delete the next node instead.

ref

class Node:
    def deleteNode(node: ListNode) -> None:
        node.val = node.next.val        # Step 1: Copy value from next node
        node.next = node.next.next      # Step 2: Skip the next node