030-linked-list-problem-3.md

Linked-list Problem 3

LeetCode: https://leetcode.com/problems/linked-list-cycle/ Difficulty: Medium

Problem

Solve this linked-list problem efficiently.

Brute Force Approach

function solve(head) {
    // Convert to array
    const arr = [];
    let curr = head;
    while (curr) {
        arr.push(curr.val);
        curr = curr.next;
    }
    
    // Process array
    // ... operations
    
    // Rebuild list
    const dummy = new ListNode(0);
    curr = dummy;
    for (const val of arr) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(head) {
    let prev = null;
    let curr = head;
    
    // In-place manipulation
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

Original: 1 → 2 → 3 → 4 → null

After operation:
null ← 1 ← 2 ← 3 ← 4
                    ↑
                   head

---

Visit LeetCode for full problem description.