递归实现：从链表末尾开始为第k个节点累加k值

给定一个整数链表和数值k，需从链表末尾开始，为每个第k个节点的数值累加k。示例如下：

• 示例1：链表为1 -> 2 -> 3 -> 4，k=3时，结果为1 -> 5 -> 3 -> 4。因为末尾第3个节点是2，累加3后得到5，其余节点不变。
• 示例2：链表为1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，k=3时，有两个节点被修改，结果为1 -> 5 -> 3 -> 4 -> 8 -> 6 -> 7。

以下是我目前写的代码，但我可能需要使用指针，且不清楚到达目标节点后如何为其累加k值：

function solution(head, k) {

  if(head == null) return head;

  if(head.next) {
    for(let i = 0; i < k; i++) {
    return solution(head.next, k)
  }
return head;
}

你当前的代码逻辑存在问题：递归里的for循环会直接返回，完全没起到计数作用。下面提供两种可行的实现思路：

递归回溯法 #

利用递归遍历到链表末尾，回溯时从尾部往回计数，每数到k的倍数位置时，给当前节点的数值累加k。

代码实现：

function solution(head, k) {
    let count = 0;
    // 递归遍历+回溯计数
    function traverse(node) {
        if (!node) return;
        // 先递归到链表最后一个节点
        traverse(node.next);
        count++;
        // 从末尾数第k、2k...个节点时，累加k
        if (count % k === 0) {
            node.val += k;
        }
    }
    traverse(head);
    return head;
}

双指针迭代法 #

通过快慢指针定位目标节点，避免递归栈溢出风险，适合长链表场景：

1. 快指针先向前走k步
2. 快慢指针同步前进，直到快指针走到链表末尾，此时慢指针的下一个节点就是从末尾数第k个节点
3. 修改该节点数值后，重置指针继续寻找下一个目标节点

代码实现：

function solution(head, k) {
    if (!head) return head;
    // 用哑节点处理边界情况
    let dummy = new ListNode(0, head);
    let slow = dummy;
    let fast = dummy;
    
    while (true) {
        // 快指针先走k步
        for (let i = 0; i < k; i++) {
            fast = fast.next;
            // 快指针走到头，说明没有更多目标节点
            if (!fast) return dummy.next;
        }
        // 快慢指针同步前进，直到快指针到末尾
        while (fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        // 修改目标节点数值
        slow.next.val += k;
        // 移动指针，准备寻找下一个目标节点
        slow = slow.next;
        fast = slow;
    }
}

内容的提问来源于stack exchange，提问作者Sharon Kaufman