1<<-DOC
  2Note: Try to solve this task in O(list size) time using O(1) additional space, since this is what you'll be asked during an interview.
  3
  4Given a singly linked list of integers l and a non-negative integer n,
  5move the last n list nodes to the beginning of the linked list.
  6
  7Example
  8
  9For l = [1, 2, 3, 4, 5] and n = 3, the output should be
 10rearrangeLastN(l, n) = [3, 4, 5, 1, 2];
 11For l = [1, 2, 3, 4, 5, 6, 7] and n = 1, the output should be
 12rearrangeLastN(l, n) = [7, 1, 2, 3, 4, 5, 6].
 13Input/Output
 14
 15[time limit] 4000ms (rb)
 16[input] linkedlist.integer l
 17
 18A singly linked list of integers.
 19
 20Guaranteed constraints:
 210 ≤ list size ≤ 105,
 22-1000 ≤ element value ≤ 1000.
 23
 24[input] integer n
 25
 26A non-negative integer.
 27
 28Guaranteed constraints:
 290 ≤ n ≤ list size.
 30
 31[output] linkedlist.integer
 32
 33Return l with the n last elements moved to the beginning.
 34DOC
 35
 36describe "#rearrange_last_n" do
 37  def length_of(list)
 38    i = 1
 39    i += 1 while list = list.next
 40    i
 41  end
 42
 43  def rearrange_last_n(list, n)
 44    return list if n.zero?
 45    length = length_of(list)
 46    return list if n == length
 47
 48    position = length - n
 49    head = mid = tail = list
 50
 51    tail = tail.next until tail.next.nil?
 52    (position - 1).times { mid = mid.next }
 53    nh = mid.next
 54    mid.next = nil
 55    tail.next = head
 56
 57    nh
 58  end
 59
 60  [
 61    { l: [1, 2, 3, 4, 5], n: 3, x: [3, 4, 5, 1, 2] },
 62    { l: [1, 2, 3, 4, 5, 6, 7], n: 1, x: [7, 1, 2, 3, 4, 5, 6] },
 63    { l: [1000, -1000], n: 0, x: [1000, -1000] },
 64    { l: [], n: 0, x: [] },
 65    { l: [123, 456, 789, 0], n: 4, x: [123, 456, 789, 0] },
 66  ].each do |x|
 67    it do
 68      result = rearrange_last_n(ListNode.to_list(x[:l]), x[:n])
 69      expect(result.to_a).to eql(x[:x])
 70    end
 71  end
 72
 73  class ListNode
 74    attr_accessor :value, :next
 75
 76    def initialize(value, next_node: nil)
 77      @value = value
 78      @next = next_node
 79    end
 80
 81    def to_a
 82      result = []
 83      current = self
 84      until current.nil?
 85        result.push(current.value)
 86        current = current.next
 87      end
 88      result
 89    end
 90
 91    def self.to_list(items)
 92      x = nil
 93      items.inject(nil) do |memo, item|
 94        node = new(item)
 95        if memo.nil?
 96          x = node
 97        else
 98          memo.next = node
 99        end
100        node
101      end
102      x
103    end
104  end
105end