Linked List Problems Collection (Java)

This blog provides solutions to four LeetCode linked list problems: 143. Reorder List, 234. Palindrome Linked List, 876. Middle of the Linked List, and 206. Reverse Linked List. Each problem is explained with its approach, edge cases, and complexity analysis, followed by a Java implementation using ListNode class:

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

1. 143. Reorder List

Leetcode 143. Reorder List

Problem Description

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…. You may not modify the values in the nodes, only the pointers. The solution must be in-place.

Example:

• Input: 1->2->3->4
• Output: 1->4->2->3
• Input: 1->2->3->4->5
• Output: 1->5->2->4->3

Approach

1. Find the Middle Node: Use the slow and fast pointer technique to find the middle of the list. For even-length lists, take the second middle node (e.g., node 3 in 1->2->3->4).
2. Reverse the Second Half: Reverse the second half of the list starting from the node after the middle (e.g., 3->4 becomes 4->3).
3. Merge the Halves: Merge the first half (1->2) and the reversed second half (4->3) by interleaving nodes (1->4->2->3).

Edge Cases

• Empty list or single node: No reordering needed.
• Two nodes: Reorder to 1->2.
• Odd or even number of nodes: Handle both cases correctly.

Complexity

• Time Complexity: O(n), where n is the number of nodes. Finding the middle takes O(n/2), reversing the second half takes O(n/2), and merging takes O(n/2).
• Space Complexity: O(1), as the solution is in-place.

Code

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

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

        // Step 2: Reverse the second half
        ListNode prev = null, curr = slow.next;
        slow.next = null; // Split the list
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: Merge the two halves
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode nextFirst = first.next;
            ListNode nextSecond = second.next;
            first.next = second;
            second.next = nextFirst;
            first = nextFirst;
            second = nextSecond;
        }
    }
}

Explanation

• Middle Node: slow ends at the middle node (e.g., node 3 in 1->2->3->4->5). The list is split by setting slow.next = null.
• Reverse Second Half: Starting from curr = slow.next, reverse the pointers (e.g., 3->4->5 becomes 5->4->3).
• Merge: Interleave nodes from first (first half) and second (reversed second half) by adjusting next pointers.

2. 234. Palindrome Linked List

Problem Description

Given a singly linked list, determine if it is a palindrome (i.e., reads the same forward and backward).

Example:

• Input: 1->2->2->1
• Output: true
• Input: 1->2
• Output: false

Approach

1. Find the Middle Node: Use slow and fast pointers to locate the middle. For even-length lists, use the second middle node.
2. Reverse the Second Half: Reverse the second half of the list in-place.
3. Compare Halves: Compare the first half with the reversed second half. If all values match, it’s a palindrome.
4. Optional Restore: The list can be restored by reversing the second half back, but this isn’t required.

Edge Cases

• Empty list or single node: Palindrome (return true).
• Two nodes: Check if values are equal.
• Odd or even length: Handle both correctly.

Complexity

• Time Complexity: O(n). Finding the middle, reversing, and comparing each take O(n/2).
• Space Complexity: O(1), as the solution is in-place.

Code

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

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

        // Step 2: Reverse the second half
        ListNode prev = null, curr = slow;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: Compare first and second halves
        ListNode first = head, second = prev;
        while (second != null) {
            if (first.val != second.val) return false;
            first = first.next;
            second = second.next;
        }
        return true;
    }
}

Explanation

• Middle Node: slow points to the middle (e.g., 2 in 1->2->2->1).
• Reverse Second Half: Reverse from slow (e.g., 2->1 becomes 1->2).
• Compare: Check if first (1->2) matches second (1->2). If any values differ, return false.

3. 876. Middle of the Linked List

Problem Description

Given a non-empty singly linked list, return the middle node. If there are two middle nodes, return the second one.

Example:

• Input: 1->2->3->4->5
• Output: 3->4->5
• Input: 1->2->3->4
• Output: 3->4

Approach

Use the slow and fast pointer technique:

• Slow pointer (p1) moves one step at a time.
• Fast pointer (p2) moves two steps at a time.
• When p2 reaches the end (or null), p1 is at the middle node. The condition p2 != null && p2.next != null ensures p1 lands on the second middle node for even-length lists.

Edge Cases

• Single node: Return the head.
• Empty list: Not applicable (problem guarantees non-empty).
• Two nodes: Return the second node.

Complexity

• Time Complexity: O(n), where n is the number of nodes (traverse half the list).
• Space Complexity: O(1), using only two pointers.

Code

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null; // Handle empty list (optional)
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }
}

Explanation

• The while (p2 != null && p2.next != null) condition prevents NullPointerException (fixing the issue in your original code with &).
• For 1->2->3->4, p1 ends at 3 (second middle node).
• For 1->2->3, p1 ends at 2.

4. 206. Reverse Linked List

Problem Description

Reverse a singly linked list.

Example:

• Input: 1->2->3->4->5
• Output: 5->4->3->2->1

Approach

Iteratively reverse the list by adjusting next pointers:

• Maintain three pointers: prev, curr, and next.
• For each node, save next, reverse the link (curr.next = prev), and move forward.

Edge Cases

• Empty list: Return null.
• Single node: Return the head.
• Multiple nodes: Reverse all links.

Complexity

• Time Complexity: O(n), where n is the number of nodes (one pass).
• Space Complexity: O(1), using only three pointers.

Code

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Explanation

• Start with prev = null, curr = head.
• For each node, save next, set curr.next = prev, update prev = curr, and move curr = next.
• Return prev as the new head (e.g., 5 in 5->4->3->2->1).