Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Linked List Revision
DSA

Linked List Revision

Quickly revise linked-list operations, pointer manipulation, and common interview techniques.

slow = head
fast = head

While fast != null AND fast.next != null:
    slow = slow.next
    fast = fast.next.next

If detecting cycle:
    If slow == fast → cycle exists

If finding middle:
    When loop ends → slow is middle

When to use

  • Detect cycle
  • Find middle of linked list
  • Find start of cycle (phase 2)

Time: O(n), Space: O(1)

public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) return true;
    }
    return false;
}

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    if head is None:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True
    return False

def find_middle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (head == nullptr) return false;

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) return true;
    }
    return false;
}

ListNode* findMiddle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function hasCycle(head) {
    if (head === null) return false;

    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) return true;
    }
    return false;
}

function findMiddle(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

2 Reverse Linked List

prev = null
current = head

While current != null:
    nextNode = current.next
    current.next = prev
    prev = current
    current = nextNode

Return prev

When to use

  • Reverse entire list
  • Sublist reversal
  • Palindrome check
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}
def reverse_list(head):
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev
ListNode* reverseList(ListNode *head) {
    ListNode *prev = nullptr;
    ListNode *current = head;

    while (current != nullptr) {
        ListNode *nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}
function reverseList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        const nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}

3 Merge Two Sorted Lists

Create dummy node
tail = dummy

While l1 != null AND l2 != null:
    If l1.val < l2.val:
        tail.next = l1
        l1 = l1.next
    Else:
        tail.next = l2
        l2 = l2.next
    tail = tail.next

Attach remaining list
Return dummy.next

When to use

  • Merge sorted lists
  • Merge k lists (extend with heap)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}
def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode dummy(0);
    ListNode *tail = &dummy;

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = (l1 != nullptr) ? l1 : l2;
    return dummy.next;
}
function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let tail = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = l1 !== null ? l1 : l2;
    return dummy.next;
}

4 Remove N-th Node From End

Create dummy pointing to head
first = dummy
second = dummy

Move first n+1 steps ahead

While first != null:
    first = first.next
    second = second.next

Delete second.next
Return dummy.next

Edge Cases

  • Removing head
  • Single node list
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode first = dummy;
    ListNode second = dummy;

    for (int i = 0; i <= n; i++) {
        first = first.next;
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
}
def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head

    first = dummy
    second = dummy

    for _ in range(n + 1):
        first = first.next

    while first:
        first = first.next
        second = second.next

    second.next = second.next.next
    return dummy.next
ListNode* removeNthFromEnd(ListNode *head, int n) {
    ListNode dummy(0);
    dummy.next = head;

    ListNode *first = &dummy;
    ListNode *second = &dummy;

    for (int i = 0; i <= n; i++) {
        first = first->next;
    }

    while (first != nullptr) {
        first = first->next;
        second = second->next;
    }

    ListNode *toDelete = second->next;
    second->next = second->next->next;
    delete toDelete;
    return dummy.next;
}
function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;

    let first = dummy;
    let second = dummy;

    for (let i = 0; i <= n; i++) {
        first = first.next;
    }

    while (first !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
}

5 Linked List Cycle Detection (With Start Node)

Phase 1:
    Detect cycle using fast/slow

Phase 2:
    Move slow to head
    Move both one step at a time
    Meeting point = cycle start
public ListNode detectCycle(ListNode head) {
    if (head == null) return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}
def detect_cycle(head):
    if head is None:
        return None

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
ListNode* detectCycle(ListNode *head) {
    if (head == nullptr) return nullptr;

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}
function detectCycle(head) {
    if (head === null) return null;

    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

6 Flatten / Reorder List (Reorder Pattern)

Find middle
Reverse second half
Merge first half and reversed half alternately

Pattern Used

  • Fast/slow
  • Reverse
  • Merge
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    // Find middle
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    ListNode second = reverseList(slow.next);
    slow.next = null;

    // Merge
    ListNode first = head;
    while (second != null) {
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}
def reorder_list(head):
    if head is None or head.next is None:
        return

    # Find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    second = reverse_list(slow.next)
    slow.next = None

    # Merge
    first = head
    while second:
        temp1 = first.next
        temp2 = second.next

        first.next = second
        second.next = temp1

        first = temp1
        second = temp2
void reorderList(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return;

    // Find middle
    ListNode *slow = head, *fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse second half
    ListNode *second = reverseList(slow->next);
    slow->next = nullptr;

    // Merge
    ListNode *first = head;
    while (second != nullptr) {
        ListNode *temp1 = first->next;
        ListNode *temp2 = second->next;

        first->next = second;
        second->next = temp1;

        first = temp1;
        second = temp2;
    }
}
function reorderList(head) {
    if (head === null || head.next === null) return;

    // Find middle
    let slow = head, fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse second half
    let second = reverseList(slow.next);
    slow.next = null;

    // Merge
    let first = head;
    while (second !== null) {
        const temp1 = first.next;
        const temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}

7 Two Pointers (Universal Pattern)

left = start
right = end

While left < right:
    process(left, right)

    Move left/right based on condition

Use Cases

  • Palindrome check
  • Pair sum
  • Partition problems
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        if (s.charAt(left) != s.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}
def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
bool isPalindrome(const std::string &s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}
function isPalindrome(s) {
    let left = 0, right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right])
            return false;
        left++;
        right--;
    }
    return true;
}

8 Hashing (Universal Detection Pattern)

Initialize set

While traversing:
    If node in set:
        cycle detected
    Add node to set

When to use

  • Detect duplicates
  • Detect cycle (extra space version)

Time: O(n) Space: O(n)

public boolean hasCycleHash(ListNode head) {
    Set<ListNode> visited = new HashSet<>();

    while (head != null) {
        if (visited.contains(head))
            return true;
        visited.add(head);
        head = head.next;
    }
    return false;
}
def has_cycle_hash(head):
    visited = set()

    while head:
        if head in visited:
            return True
        visited.add(head)
        head = head.next
    return False
bool hasCycleHash(ListNode *head) {
    std::unordered_set<ListNode*> visited;

    while (head != nullptr) {
        if (visited.count(head))
            return true;
        visited.insert(head);
        head = head->next;
    }
    return false;
}
function hasCycleHash(head) {
    const visited = new Set();

    while (head !== null) {
        if (visited.has(head))
            return true;
        visited.add(head);
        head = head.next;
    }
    return false;
}

My Private Notes

Notes are auto-saved locally to this device.