Two Pointers For A Linear Solution II

Two-pointers is a common technique to solving problems in O(n)-time and O(1)-space. It has been demonstrated here before: https://anothercasualcoder.blogspot.com/2018/09/two-pointers-for-linear-solution.html

Problem today is this one:

This problem was asked by Google.

Given a singly linked list and an integer k, remove the k^th last element from the list. k is guaranteed to be smaller than the length of the list.

The list is very long, so making more than one pass is prohibitively expensive.

Do this in constant space and in one pass.

Strategy: keep track of a "behind" node and also a "previousBehind" node. Have another node which is running thru the list and once a counter goes beyond k, start moving the two behind pointers. Once the third pointer hits the end of the list, you're ready to delete the "behind" node using the previous pointer.

Code is here and down below too, cheers, Marcelo

https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10102018.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
 class DailyCodingProblem10102018
 {
  private MyList list = null;

  public DailyCodingProblem10102018(int n)
  {
   Random rd = new Random();

   list = new MyList(rd.Next(0, 100));
   MyList current = list;
   for (int i = 1; i < n; i++)
   {
    current.next = new MyList(rd.Next(0, 100));
    current = current.next;
   }
  }

  public void DeleteK(int k)
  {
   PrintList();

   MyList previousBehind = null;
   MyList currentBehind = null;

   int count = 1;
   for (MyList current = list; current != null; current = current.next)
   {
    if (count >= k)
    {
     if (currentBehind == null)
     {
      currentBehind = list;
     }
     else
     {
      previousBehind = currentBehind;
      currentBehind = currentBehind.next;
     }
    }
    count++;
   }

   if (previousBehind == null)
   {
    list = currentBehind.next;
   }
   else
   {
    previousBehind.next = currentBehind.next;
   }

   PrintList();
  }

  public void PrintList()
  {
   for (MyList l = list; l != null; l = l.next)
   {
    Console.Write("{0} ", l.val);
   }
   Console.WriteLine();
  }
 }
}