19. Remove nth from back

19_solution1.c

#include "list_node.h"
#include <stdlib.h>

struct ListNode *removeNthFromEnd(struct ListNode *head, int n) {
  struct ListNode dummy = {0, head};
  struct ListNode *left = &dummy;
  struct ListNode *right = &dummy;

  // create a gap of n nodes between left and right
  for (int i = 0; i < n; i++)
    right = right->next;

  // move both until right is on the last node;
  // left is then on the node before the target
  while (right->next) {
    right = right->next;
    left = left->next;
  }

  struct ListNode *target = left->next;
  left->next = target->next;
  free(target);

  return dummy.next;
}

list_node.h

#pragma once

#include <stddef.h>

// Definition for singly-linked list.
struct ListNode {
  int val;
  struct ListNode *next;
};

19_solution1.cpp

#include "list_node.h"

class Solution {
public:
  ListNode *removeNthFromEnd(ListNode *head, int n) {
    ListNode dummy(0, head);
    ListNode *left = &dummy;
    ListNode *right = &dummy;

    if (!head || n <= 0)
      return head;

    for (int i = 0; i < n; i++)
      right = right->next;

    while (right->next) {
      right = right->next;
      left = left->next;
    }

    ListNode *target = left->next;
    left->next = target->next;
    delete target;

    return dummy.next;
  }
};

list_node.h

#pragma once

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

19_solution1.go

package linkedlists

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    left := dummy
    right := dummy

    // create a gap of n nodes between left and right
    for i := 0; i < n; i++ {
        right = right.Next
    }

    // move both until right is on the last node;
    // left is then on the node before the target
    for right.Next != nil {
        right = right.Next
        left = left.Next
    }

    left.Next = left.Next.Next

    return dummy.Next
}

list_node.go

package linkedlists

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

19_solution1.java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = dummy;

        // create a gap of n nodes between left and right
        for (int i = 0; i < n; i++)
            right = right.next;

        // move both until right is on the last node;
        // left is then on the node before the target
        while (right.next != null) {
            right = right.next;
            left = left.next;
        }

        left.next = left.next.next;

        return dummy.next;
    }
}

ListNode.java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

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

19_solution1.js

const ListNode = require("./list_node");

var removeNthFromEnd = function (head, n) {
  const dummy = new ListNode(0, head);
  let left = dummy;
  let right = dummy;

  // create a gap of n nodes between left and right
  for (let i = 0; i < n; i++) right = right.next;

  // move both until right is on the last node;
  // left is then on the node before the target
  while (right.next) {
    right = right.next;
    left = left.next;
  }

  left.next = left.next.next;

  return dummy.next;
};

list_node.js

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

module.exports = ListNode;

19_solution1.py

from typing import Optional

from list_node import ListNode


class Solution:
    def removeNthFromEnd(
        self, head: Optional[ListNode], n: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left = dummy
        right = dummy

        # create a gap of n nodes between left and right
        for _ in range(n):
            right = right.next

        # move both until right is on the last node;
        # left is then on the node before the target
        while right.next:
            right = right.next
            left = left.next

        left.next = left.next.next

        return dummy.next

list_node.py

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

19_solution1.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode { val: 0, next: head });

        // count the nodes to find the index of the node before the target
        let mut len = 0;
        let mut cur = dummy.next.as_ref();
        while let Some(node) = cur {
            len += 1;
            cur = node.next.as_ref();
        }

        let mut prev = &mut dummy;
        for _ in 0..(len - n) {
            prev = prev.next.as_mut().unwrap();
        }

        let target = prev.next.take();
        prev.next = target.and_then(|node| node.next);

        dummy.next
    }
}

list_node.rs

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}