Add k to the kTh node, starting from the end Recursively-CodePudding

Given a linked list of integers and a number, k, add k to every kth node starting from the end. For example, if the list is [1 -> 2 -> 3 -> 4] and k is 3, then the result is [1 -> 5 -> 3 -> 4]. The 2 was the third value from the end, we added three to get 5. No other nodes are modified.

For a longer example, consider the list:

[1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7] If k=3, two nodes change:

[1 -> 5 -> 3 -> 4 -> 8 -> 6 -> 7]

Here's what I have so far, but I should probably be using some pointers and I can't figure out how to add k to the kth element once we reach it.

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;
}

CodePudding user response：

If you do not know the length or end node of the linked list, then you first need to find it by looping through it. From there, you can then loop through the linked list again and add k to the node's value if the length minus the node's index is divisible by k. Like this:

function solution(head, k) {
  // Get length of the list
  let len = 0;
  let ptr = head;
  while (ptr !== null) {
    ptr = ptr.next;
    len  ;
  }

  // Loop through list and change nodes
  // with indices that satisfy condition
  ptr = head;
  let i = 0;
  while (ptr !== null) {
    if ((len-i) % k === 0) ptr.value  = k;
    i  ;
    ptr = ptr.next;
  }
  return head;
}

Note: My code assumes the value of the node is stored in the .value property. You may need to change this.

CodePudding user response：

You can get the length of the linked list, then calculate which nodes to increment based on their indexes.

function arrToLinkedList(arr) {
  let head = arr.length ? {value: arr[0]} : null, curr = head;
  for (let i = 1; i < arr.length; i  ) curr.next = {value: arr[i]}, curr = curr.next;
  return head;
}
function linkedListToArr(head) {
  const res = [];
  for (let curr = head; curr; curr = curr.next) res.push(curr.value);
  return res;
}
function solution(head, k) {
  let len = 0, curr = head;
  while (curr)   len, curr = curr.next;
  curr = head;
  for (let i = 0; i < len - 1; i  ) {
    if ((len - i) % k === 0) curr.value  = k;
    curr = curr.next;
  }
  return head;
}
console.log(linkedListToArr(solution(arrToLinkedList([1, 2, 3, 4, 5, 6, 7]), 3)));