// In this problem, you need to implement a function
// `removeEverySecondNode` that accepts a singly linked list
// as an argument. The function should remove every alternate
// node, starting with the second node.

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

function printLinkedList(head) {
  let currentNode = head;
  let listStr = '';
  while (currentNode !== null) {
    listStr += currentNode.val + ' -> ';
    currentNode = currentNode.next;
  }
  listStr += 'null';
  console.log(listStr);
}

function createLinkedList(arr) {
  let head = new ListNode(0);
  let current = head;
  arr.forEach(val => {
    current.next = new ListNode(val);
    current = current.next;
  });
  return head.next;
}

let list1 = createLinkedList([1, 2, 3, 4, 5]);
let list2 = createLinkedList([1, 2]);
let list3 = createLinkedList([1]);
let list4 = createLinkedList([1, 2, 3, 4]);
let list5 = createLinkedList([]);

printLinkedList(removeEverySecondNode(list1)); // Expected: 1 -> 3 -> 5 -> null
printLinkedList(removeEverySecondNode(list2)); // Expected: 1 -> null
printLinkedList(removeEverySecondNode(list3)); // Expected: 1 -> null
printLinkedList(removeEverySecondNode(list4)); // Expected: 1 -> 3 -> null
printLinkedList(removeEverySecondNode(list5)); // Expected: null

Exercises

1. Solve the "Remove Every Second" problem. Remember, you need to mutate the given linked list, not create a new one.

   Ask LSBot for a Hint

   Share your work-in-progress with LSBot

   Share what you have so far, or tell LSBot what you need help with.

   Formatting Help

   Preview

   Submit

   Open Hint Conversation

   Edit Edit your hint request before submitting to LSBot
   Ask LSBot for a Code Review

   Share your completed work with LSBot

   Have LSBot review your solution and suggest improvements.

   This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot and get email notifications when LSBot reviews your solutions.

   Formatting Help

   Preview Submit for Review

   Edit Edit your content before submitting to LSBot

   View Our Solution

   To solve this problem, we'll use a curr pointer that will start at head.

   We will traverse the linked list and adjust the next pointer of a given node so that it skips over the immediate next node. We can accomplish this via curr.next = curr.next.next. This operation effectively removes the node referenced by curr.next from the linked list by bypassing it.

   After performing this removal, we'll move curr forward to continue the process from the newly adjusted position in the list (curr = curr.next). This step is crucial as it maintains the continuity of the traversal, essentially moving the point of operation one step ahead in the list.

   The process concludes when we encounter a scenario where curr or curr.next is null, indicating we have reached the end of the list or there are no more nodes to skip. Finally, we can return the head node, which is the starting point of the modified list.

   ---

   Let's see this visually:

   We are given a linked list 1 -> 2 -> 3 -> 4 -> 5, and our goal is to remove every second node, resulting in the list 1 -> 3 -> 5.

   

   Initializing the Necessary Variables

   For this problem, we only need to introduce one additional variable, curr, which will keep track of the current node in the list. We will initialize curr to the head node. It's important to note that we cannot use the head node for tracking purposes because if we were to move its reference, we would lose the reference to the head node (the node with the value 1 in this case).

   

   Step 1

   We are starting with both head and curr pointing at the node 1.

   

   Since we want to skip the second node, we need to adjust the link so that curr.next points tocurr.next.next.

   

   After we do this, we only need to slide the curr pointer (curr = curr.next). curr.next previously referenced the node with value 2, but now that we've deleted this node, curr.next references the node with value 3.

   

   Step 2

   Our work for the second iteration is much the same. curr references the node with value 3.

   

   We want to skip the second node, so we need to adjust the link so that curr.next points tocurr.next.next.

   

   After we do this, we slide the curr pointer (curr = curr.next).

   

   Step 3

   We have reached the condition where curr.next is pointing to null.

   

   Therefore, we exit the loop and return the head node which is our result list 1 -> 3 -> 5 -> null.

   

   Solution Code

   function removeEverySecondNode(head) {
     let curr = head;
     while (curr && curr.next) {
       curr.next = curr.next.next;
       curr = curr.next;
     }
     return head;
   }