1<<-DOC
  2Note: Try to solve this task in O(n) time using O(1) additional space, where n is the number of elements in the list, since this is what you'll be asked to do during an interview.
  3
  4Given a singly linked list of integers l and an integer k, remove all elements from list l that have a value equal to k.
  5
  6Example
  7
  8For l = [3, 1, 2, 3, 4, 5] and k = 3, the output should be
  9removeKFromList(l, k) = [1, 2, 4, 5];
 10For l = [1, 2, 3, 4, 5, 6, 7] and k = 10, the output should be
 11removeKFromList(l, k) = [1, 2, 3, 4, 5, 6, 7].
 12Input/Output
 13
 14[time limit] 4000ms (rb)
 15[input] linkedlist.integer l
 16
 17A singly linked list of integers.
 18
 19Guaranteed constraints:
 200 ≤ list size ≤ 105,
 21-1000 ≤ element value ≤ 1000.
 22
 23[input] integer k
 24
 25An integer.
 26
 27Guaranteed constraints:
 28-1000 ≤ k ≤ 1000.
 29
 30[output] linkedlist.integer
 31
 32Return l with all the values equal to k removed.
 33DOC
 34
 35describe "remove_k_from_list" do
 36  def remove_k_from_list(head, target)
 37    current = head
 38    previous = nil
 39
 40    until current.nil?
 41      if current.value == target
 42        if previous.nil?
 43          head = current.next
 44          current = head
 45        else
 46          previous.next = current.next
 47          current = current.next
 48        end
 49      else
 50        previous = current
 51        current = current.next
 52      end
 53    end
 54    head
 55  end
 56
 57  def not_target(head, target)
 58    head = head.next while head && head.value == target
 59    head
 60  end
 61
 62  def remove_k_from_list(head, target)
 63    head = node = not_target(head, target)
 64    while node
 65      node.next = not_target(node.next, target)
 66      node = node.next
 67    end
 68    head
 69  end
 70
 71  class ListNode
 72    attr_accessor :value, :next
 73
 74    def initialize(value, next_node: nil)
 75      @value = value
 76      @next = next_node
 77    end
 78
 79    def to_a
 80      result = []
 81      current = self
 82      until current.nil?
 83        result.push(current.value)
 84        current = current.next
 85      end
 86      result
 87    end
 88  end
 89
 90  def to_list(items)
 91    x = nil
 92    items.inject(nil) do |memo, item|
 93      node = ListNode.new(item)
 94      if memo.nil?
 95        x = node
 96      else
 97        memo.next = node
 98      end
 99      node
100    end
101    x
102  end
103
104  [
105    { l: [3, 1, 2, 3, 4, 5], k: 3, x: [1, 2, 4, 5] },
106    { l: [1, 2, 3, 4, 5, 6, 7], k: 10, x: [1, 2, 3, 4, 5, 6, 7] },
107    { l: [1000, 1000], k: 1000, x: [] },
108    { l: [], k: -1000, x: [] },
109    { l: [123, 456, 789, 0], k: 0, x: [123, 456, 789] },
110  ].each do |x|
111    it do
112      list = to_list(x[:l])
113      expect(remove_k_from_list(list, x[:k]).to_a).to eql(x[:x])
114    end
115  end
116end