LeetCode Java Implementations

The 'Reverse Nodes in k-Group' problem involves reversing a linked list in segments of size k. If the number of nodes remaining is less than k, those nodes should remain in their original order.

Logic Overview

1. Identify Segments: Iterate through the list using a pointer (cur) and a counter (count) to find segments of length k.
2. Reverse Segment: Once k nodes are identified, use a reversal method (similar to reversing a standard singly linked list) to flip the direction of the pointers within that segment.
3. Reconnect Segments:
   • Connect the tail of the previously reversed segment to the head of the newly reversed segment.
   • Connect the tail of the newly reversed segment to the start of the next segment.
4. Handle the Head: Maintain a reference to the new head of the entire list (the head of the first reversed segment) to return it at the end.

For the complete implementation, refer to ReverseNodesInkGroup.java in the same directory.

To reverse a singly linked list, use an iterative approach with three pointers: pre (previous), cur (current), and next (temporary storage for the next node).

Implementation Steps

1. Edge Case Check: If the head is null or head.next is null, the list is empty or has only one node. Return head immediately.
2. Pointer Initialization:
   • pre: Initialized to null (this will become the new tail).
   • cur: Initialized to head (the starting point of traversal).
3. Iteration Loop: While cur is not null, perform the following four steps in order:
   • Store Next: Save the next node to prevent losing the reference: ListNode next = cur.next;
   • Reverse Pointer: Point the current node's next reference to the previous node: cur.next = pre;
   • Advance Previous: Move the pre pointer forward to the current node: pre = cur;
   • Advance Current: Move the cur pointer forward to the saved next node: cur = next;
4. Return: Once the loop finishes, pre will point to the new head of the reversed list.

Key Concept: Assignment vs. Reference

• next = cur.next: Assigns the value of the next node to a temporary variable.
• cur.next = pre: Assigns the reference of the pre node to the cur.next pointer, effectively reversing the direction.

This approach treats the problem as $n$ decision stages. For each item, you have two choices: include it or exclude it. To avoid redundant calculations in the resulting recursion tree, use a memoization table mem[i][curLoadSum] to store whether a specific state (current item index and current total weight) has already been visited.

Key logic:

• Base Case: If the current weight equals bw or all items have been considered, update the maximum weight found.
• Pruning: If adding an item would exceed bw, do not proceed with that branch.
• Memoization: Check mem[i][curLoadSum] before proceeding to avoid re-calculating known states.

/**
     * 解法1 回溯 + 记忆化递归
     *
     * @param i: 考察到哪个物品
     * @param curLoadSum: 当前已经装进去的物品的重量和
     * @param n：物品个数
     * @param bpWeight：背包可承受重量
     */
    private void f(int i, int curLoadSum, int n, int bpWeight) {
        if (curLoadSum == bw || i == n) {
            maxW = Math.max(maxW, curLoadSum);
            return;
        }
        if (mem[i][curLoadSum]) return;
        mem[i][curLoadSum] = true;
        f(i + 1, curLoadSum, n, bpWeight); // 不装第 i 件物品
        if (curLoadSum + weights[i] <= bw) // 剪枝
            f(i + 1, curLoadSum + weights[i], n, bpWeight); // 装第 i 件物品
    }

This guide explains the mathematical approach to solving LeetCode 142: finding the specific node where a cycle begins in a linked list.

Algorithm Logic

1. Detect the Cycle: Use two pointers, fast (moves two steps) and low (moves one step). If they meet, a cycle exists.
2. Calculate the Entry Point:
   • Let $x$ be the distance from the start node to the cycle entry point.
   • Let $y$ be the distance from the entry point to the meeting point.
   • Let $z$ be the distance from the meeting point back to the entry point.
   • Based on the relationship between these distances, once the pointers meet, resetting one pointer to the start node and moving both pointers one step at a time will result in them meeting exactly at the cycle's entry point.

Implementation Strategy

• Start fast and low at the head.
• Move fast by 2 and low by 1 until they meet.
• If they meet, reset fast to the head node.
• Move both fast and low by 1 step at a time. The node where they meet is the entry point of the cycle.

Dynamic Programming (DP) solves the problem by tracking all possible reachable weights at each stage (each item).

Implementation Details:

1. Use a 2D boolean array s[n][bw + 1] where s[i][j] is true if weight j can be achieved using a subset of the first i items.
2. Initialization: Set s[0][0] = true (not picking the first item) and, if the first item's weight is $\le$ bw, set s[0][weights[0]] = true (picking the first item).
3. Transitions: For each subsequent item i:
   • Exclude item i: Carry over all reachable weights from the previous stage: s[i][j] = s[i-1][j].
   • Include item i: For every weight j reachable in the previous stage, mark j + weights[i] as reachable in the current stage, provided it doesn't exceed bw.
4. Result: After processing all items, iterate backwards from bw to 0 in the last row of the DP table. The first index i where s[n-1][i] is true is the maximum weight.

/**
     * 解法2 动态规划
     *
     * @param n：物品个数
     * @param bw: 当前已经装进去的物品的重量和
     * @return 最大可以装多少重量
     */
    private int dpBackpack (int n, int bw) {
        boolean[][] s = new boolean[n][bw + 1];
        s[0][0] = true;
        if (weights[0] <= bw) s[0][weights[0]] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= bw ; j++) {
                if (s[i - 1][j]) s[i][j] = s[i - 1][j];
            }
            for (int j = 0; j <= bw - weights[i]; j++) {
                if (s[i - 1][j]) s[i][j + weights[i]] = true;
            }
        }

        for (int i = bw; i >= 0; i--) {
            if (s[n - 1][i]) return i;
        }
        return 0;
    }