Palindrome Linked List

🎯

Palindrome Linked List

easyTWO_POINTERAmazonFacebookMicrosoft

Imagine you have a chain of beads and want to check if the sequence of colors reads the same forwards and backwards without rearranging them.

💡 This problem tests your understanding of linked lists and two-pointer techniques. Beginners often struggle because linked lists don't allow direct indexing, making it tricky to compare elements from both ends efficiently.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list is a palindrome. Return true if it is, and false otherwise.

1 ≤ n ≤ 10^5Node values are integersExpected time complexity: O(n)Expected space complexity: O(1) or O(n) depending on approach

💡

Example

Input"head = [1, 2, 2, 1]"

Outputtrue

The list reads the same forwards and backwards.

Input"head = [1, 2]"

Outputfalse

The list is not the same forwards and backwards.

• Single node list → true
• List with all identical elements → true
• List with two different elements → false
• Empty list (if allowed) → true

⚠️

Common Mistakes

Not handling odd length lists correctly

Incorrect comparison leading to false negatives

✅ Skip the middle element when list length is odd before comparison

Not restoring the list after reversing second half

Modifies input list unexpectedly, which may cause issues in real applications

✅ Reverse the second half again after comparison to restore original list

Using extra space unnecessarily in optimal approach

Fails to meet O(1) space requirement

✅ Avoid stacks or arrays; reverse second half in place instead

Incorrectly finding the midpoint with fast and slow pointers

Leads to wrong half being reversed or compared

✅ Advance fast pointer by two steps and slow by one until fast reaches end

Not checking for empty or single node lists

Code may crash or return wrong result

✅ Add base case checks for empty or single node lists returning true

🧠

Brute Force (Using Array Conversion)

💡 This approach exists to build intuition by simplifying the problem to array palindrome checking, which is easier to understand and implement for beginners.

Intuition

Convert the linked list into an array and then check if the array is a palindrome by comparing elements from both ends.

Algorithm

1. Traverse the linked list and copy all node values into an array.
2. Use two pointers, one at the start and one at the end of the array.
3. Compare elements at these pointers; if they differ, return false.
4. If all pairs match, return true.

💡 This algorithm is straightforward but requires extra space. It helps beginners understand the palindrome concept before optimizing.

</>

Code

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

def isPalindrome(head):
    vals = []
    current = head
    while current:
        vals.append(current.val)
        current = current.next
    left, right = 0, len(vals) - 1
    while left < right:
        if vals[left] != vals[right]:
            return False
        left += 1
        right -= 1
    return True

# Example usage:
if __name__ == '__main__':
    # Create linked list 1->2->2->1
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

vals = []Initialize an empty list to store node values for easy access.

while current:Traverse the linked list to collect all values.

if vals[left] != vals[right]:Check if the current pair of elements differ, indicating not a palindrome.

return TrueIf all pairs match, confirm the list is a palindrome.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> vals = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            vals.add(current.val);
            current = current.next;
        }
        int left = 0, right = vals.size() - 1;
        while (left < right) {
            if (!vals.get(left).equals(vals.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

ArrayList<Integer> vals = new ArrayList<>();Use dynamic array to store node values for random access.

while (current != null)Traverse the linked list to collect values.

if (!vals.get(left).equals(vals.get(right)))Compare elements from both ends to check palindrome property.

return true;Return true if all pairs match, confirming palindrome.

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool isPalindrome(ListNode* head) {
    vector<int> vals;
    ListNode* current = head;
    while (current != nullptr) {
        vals.push_back(current->val);
        current = current->next;
    }
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        if (vals[left] != vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

vector<int> vals;Store node values in a vector for indexed access.

while (current != nullptr)Traverse linked list to collect values.

if (vals[left] != vals[right])Compare elements from both ends to detect mismatch.

return true;Return true if no mismatches found, confirming palindrome.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function isPalindrome(head) {
    const vals = [];
    let current = head;
    while (current !== null) {
        vals.push(current.val);
        current = current.next;
    }
    let left = 0, right = vals.length - 1;
    while (left < right) {
        if (vals[left] !== vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const vals = [];Create an array to hold node values for easy palindrome check.

while (current !== null)Traverse the linked list to collect all values.

if (vals[left] !== vals[right])Check if current pair of values differ, indicating not palindrome.

return true;Return true if all pairs match, confirming palindrome.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once to copy values (O(n)) and then check palindrome in O(n). Extra space is used for the array of size n.

💡 For n=100,000 nodes, this means 100,000 operations to copy and 100,000 to check, which is feasible but uses extra memory.

Interview Verdict: Accepted

This approach works but uses extra space, which might not be optimal for very large inputs.

🧠

Better (Fast & Slow Pointer + Stack)

💡 This approach improves space usage by only storing half the list's values, introducing the fast and slow pointer technique to find the midpoint.

Intuition

Use two pointers to find the middle of the list. Push the first half's values onto a stack, then compare the second half with the stack's top elements.

Algorithm

1. Initialize fast and slow pointers at head.
2. Move fast by two steps and slow by one step, pushing slow's values onto a stack.
3. When fast reaches the end, slow is at midpoint.
4. If list length is odd, skip the middle element.
5. Compare remaining list nodes with stack's top values.
6. If all match, return true; else false.

💡 This algorithm cleverly uses a stack to reverse the first half's values, enabling comparison without full array storage.

</>

Code

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

def isPalindrome(head):
    slow = fast = head
    stack = []
    while fast and fast.next:
        stack.append(slow.val)
        slow = slow.next
        fast = fast.next.next
    if fast:  # Odd length, skip middle
        slow = slow.next
    while slow:
        top = stack.pop()
        if top != slow.val:
            return False
        slow = slow.next
    return True

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

slow = fast = headInitialize two pointers to find midpoint efficiently.

while fast and fast.next:Advance fast by two and slow by one to find middle.

stack.append(slow.val)Store first half values to compare later.

if fast: # Odd length, skip middleSkip the middle element for odd-length lists.

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) { // Odd length
            slow = slow.next;
        }
        while (slow != null) {
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Use stack to store first half values for reverse comparison.

while (fast != null && fast.next != null)Move fast and slow pointers to find midpoint.

if (fast != null) { // Odd lengthSkip middle element for odd-length lists.

if (stack.pop() != slow.val)Compare second half values with stack top.

#include <iostream>
#include <stack>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool isPalindrome(ListNode* head) {
    stack<int> st;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast != nullptr) { // Odd length
        slow = slow->next;
    }
    while (slow != nullptr) {
        if (st.top() != slow->val) {
            return false;
        }
        st.pop();
        slow = slow->next;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

stack<int> st;Stack stores first half values for reverse order comparison.

while (fast != nullptr && fast->next != nullptr)Find midpoint using fast and slow pointers.

if (fast != nullptr) { // Odd lengthSkip middle node for odd-length lists.

if (st.top() != slow->val)Compare second half nodes with stack top values.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function isPalindrome(head) {
    let slow = head, fast = head;
    const stack = [];
    while (fast !== null && fast.next !== null) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast !== null) { // Odd length
        slow = slow.next;
    }
    while (slow !== null) {
        if (stack.pop() !== slow.val) {
            return false;
        }
        slow = slow.next;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const stack = [];Stack holds first half values for reverse comparison.

while (fast !== null && fast.next !== null)Use fast and slow pointers to find midpoint.

if (fast !== null) { // Odd lengthSkip middle node for odd-length lists.

if (stack.pop() !== slow.val)Compare second half values with stack top.

⏱

Complexity

TimeO(n)

SpaceO(n/2) = O(n)

We traverse the list once to find midpoint and push half values onto stack, then compare second half in O(n). Space is reduced to half compared to brute force.

💡 For n=100,000, this means 50,000 values stored in stack, which is better but still uses extra memory.

Interview Verdict: Accepted

This approach is better than brute force in space but still not optimal for very large inputs.

🧠

Optimal (Reverse Second Half In-Place)

💡 This approach optimizes space by reversing the second half of the list in place, allowing direct comparison without extra memory.

Intuition

Find the middle of the list, reverse the second half in place, then compare the first half and reversed second half node by node.

Algorithm

1. Use fast and slow pointers to find the middle of the list.
2. Reverse the second half of the list starting from slow pointer.
3. Compare nodes from the start and from the reversed second half.
4. If all nodes match, the list is a palindrome.
5. Restore the list by reversing the second half again (optional).
6. Return the result.

💡 This algorithm is tricky because it modifies the list temporarily but uses constant space and linear time.

</>

Code

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

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

def isPalindrome(head):
    if not head or not head.next:
        return True
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second_half_start = reverse(slow)
    first_half_start = head
    second_half_copy = second_half_start
    result = True
    while second_half_start:
        if first_half_start.val != second_half_start.val:
            result = False
            break
        first_half_start = first_half_start.next
        second_half_start = second_half_start.next
    reverse(second_half_copy)  # Optional: restore list
    return result

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

def reverse(head):Helper function to reverse a linked list segment in place.

while fast and fast.next:Find midpoint using fast and slow pointers.

second_half_start = reverse(slow)Reverse second half starting from midpoint.

while second_half_start:Compare nodes from first half and reversed second half.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHalfStart = reverse(slow);
        ListNode firstHalfStart = head;
        ListNode secondHalfCopy = secondHalfStart;
        boolean result = true;
        while (secondHalfStart != null) {
            if (firstHalfStart.val != secondHalfStart.val) {
                result = false;
                break;
            }
            firstHalfStart = firstHalfStart.next;
            secondHalfStart = secondHalfStart.next;
        }
        reverse(secondHalfCopy); // Optional restore
        return result;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

private ListNode reverse(ListNode head)Reverse linked list segment in place to compare halves.

while (fast != null && fast.next != null)Find midpoint with fast and slow pointers.

ListNode secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart != null)Compare nodes from first half and reversed second half.

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* secondHalfStart = reverse(slow);
    ListNode* firstHalfStart = head;
    ListNode* secondHalfCopy = secondHalfStart;
    bool result = true;
    while (secondHalfStart) {
        if (firstHalfStart->val != secondHalfStart->val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart->next;
        secondHalfStart = secondHalfStart->next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

ListNode* reverse(ListNode* head)Reverse linked list segment in place for comparison.

while (fast && fast->next)Find midpoint using fast and slow pointers.

ListNode* secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart)Compare nodes from first half and reversed second half.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverse(head) {
    let prev = null;
    let current = head;
    while (current !== null) {
        let nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

function isPalindrome(head) {
    if (!head || !head.next) return true;
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let secondHalfStart = reverse(slow);
    let firstHalfStart = head;
    let secondHalfCopy = secondHalfStart;
    let result = true;
    while (secondHalfStart !== null) {
        if (firstHalfStart.val !== secondHalfStart.val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart.next;
        secondHalfStart = secondHalfStart.next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

function reverse(head)Reverse linked list segment in place for direct comparison.

while (fast !== null && fast.next !== null)Find midpoint using fast and slow pointers.

let secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart !== null)Compare nodes from first half and reversed second half.

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list to find midpoint, reverse half in place, and compare nodes, all in linear time with constant extra space.

💡 For n=100,000, this means 100,000 operations but minimal memory usage, making it scalable.

Interview Verdict: Accepted

This is the best approach for interviews as it meets optimal time and space requirements.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal in-place reversal approach impresses most, but understanding brute force and stack methods helps build intuition.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - never code
2. Fast & Slow Pointer + Stack	O(n)	O(n/2)	No	N/A	Good to mention as improvement, but not optimal
3. Reverse Second Half In-Place	O(n)	O(1)	No	Yes (optional)	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss improvements using fast and slow pointers with a stack.Step 4: Explain the optimal in-place reversal approach.Step 5: Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your grasp of linked list traversal, two-pointer technique, space-time tradeoffs, and ability to write clean, bug-free code.

Common Follow-ups

• What if you cannot modify the linked list? → Use stack approach.
• How to restore the list after checking? → Reverse second half again.
• What if the list is doubly linked? → Could compare from both ends directly.
• Can you do it recursively? → Yes, but watch for stack overflow.

💡 These follow-ups test your flexibility and deeper understanding of the problem constraints and variations.

🔍

Pattern Recognition

When to Use

1) Need to check palindrome property on linked list; 2) No direct indexing available; 3) Fast and slow pointers can find midpoint; 4) Reversing part of list is feasible.

Signature Phrases

'determine if linked list is palindrome''fast and slow pointers''reverse second half'

NOT This Pattern When

Problems that require full sorting or dynamic programming are different patterns.

Similar Problems

Palindrome Number - similar palindrome check but on integer digitsLinked List Cycle - uses fast and slow pointers to detect cycles

Practice

1. You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is exactly one duplicate number but it could be repeated multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Sort the array and then scan for consecutive duplicates

B. Use two pointers moving at different speeds to detect a cycle in the array values

C. Use a hash set to track seen numbers and return the first duplicate

D. Use nested loops to compare every pair of elements

Solution

1. Step 1: Understand the problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate. The input cannot be modified and extra space must be O(1).

2. Step 2: Identify the approach that fits constraints

   Sorting modifies the array, hash sets use extra space, nested loops are O(n²). Floyd's cycle detection uses two pointers at different speeds to find a cycle in O(n) time and O(1) space without modifying the array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer cycle detection fits all constraints [OK]

Hint: Cycle detection fits O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is allowed despite input constraints
• Believing hash sets use constant space
• Thinking nested loops are efficient enough

2. Given the following code snippet, what is the output when calling findDuplicate([3,1,3,4,2])?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace first phase to find intersection point

   Initialize slow=3, fast=3 (nums[0]=3). Iteration 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2. Iteration 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4. Iteration 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3. They meet at 3.

2. Step 2: Trace second phase to find cycle entrance

   Reset slow=nums[0]=3. Since slow==fast==3, loop ends immediately. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection returns duplicate 3 correctly [OK]

Hint: Cycle detection returns the duplicate value where pointers meet [OK]

Common Mistakes:

• Confusing slow and fast pointer updates
• Off-by-one errors in indexing
• Returning the wrong pointer value

3. Consider the following Python code that removes the 2nd node from the end of the list 1 -> 2 -> 3 -> 4 -> 5. What is the printed output after execution?

easy

A. 1 2 4 5

B. 1 2 3 5

C. 1 3 4 5

D. 2 3 4 5

Solution

1. Step 1: Trace recursion from end

   Recursion returns indices from the end: node 5 returns 1, node 4 returns 2, node 3 returns 3, etc.

2. Step 2: Identify node to remove

   When idx == n+1 = 3, node 3's next pointer skips node 4, effectively removing node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches list with 4 removed: 1 2 3 5 [OK]

Hint: Recursion index counts from end; remove node at idx = n+1 [OK]

Common Mistakes:

• Removing the node at idx == n instead of n+1
• Off-by-one errors in recursion index
• Confusing which node to skip

4. You are given a singly linked list and an integer k. The task is to split the list into k consecutive parts such that the sizes of the parts differ by at most one, and the earlier parts are larger if sizes differ. Which algorithmic approach best guarantees an optimal solution with minimal passes over the list?

easy

A. Greedy approach that assigns nodes to parts until each part reaches an average size, without pre-counting total nodes.

B. Dynamic programming to find the optimal partition minimizing size differences between parts.

C. Repeatedly remove nodes from the front and append to parts until all nodes are distributed, without precomputing sizes.

D. Calculate total nodes first, then split the list in one pass using precomputed part sizes and carefully breaking links.

Solution

1. Step 1: Understand problem constraints

   The problem requires splitting into k parts with sizes differing by at most one, favoring earlier parts to be larger.

2. Step 2: Identify approach that meets constraints efficiently

   Calculating total nodes first allows precise part sizes and a single pass to split, ensuring correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Precomputing sizes avoids guesswork and multiple passes [OK]

Hint: Precompute total nodes to split correctly in one pass [OK]

Common Mistakes:

• Assuming greedy without counting nodes works
• Trying DP unnecessarily
• Splitting without breaking links properly

5. If the linked list nodes cannot be modified (no extra fields allowed) and you want to detect a cycle in O(1) space, which approach correctly adapts Floyd's cycle detection algorithm to also find the entry point of the cycle?

hard

A. Use a hash set to store nodes and find the first repeated node as the cycle start.

B. Modify node values temporarily to mark visited nodes and revert after detection.

C. After detecting the cycle, reset slow to head and move both pointers one step at a time until they meet; the meeting point is the cycle start.

D. Run the fast pointer twice as fast until it reaches the end, then backtrack to find the cycle start.

Solution

1. Step 1: Detect cycle using fast and slow pointers

   When fast and slow meet, a cycle exists but the meeting point is not necessarily the cycle start.

2. Step 2: Find cycle entry point

   Reset slow to head, then move slow and fast one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard Floyd's algorithm extension for cycle entry detection [OK]

Hint: Reset slow to head after detection to find cycle start [OK]

Common Mistakes:

• Using extra memory when O(1) space required
• Modifying node values disallowed
• Incorrect pointer movement after detection