Search code examples
algorithmrecursiondata-structuressingly-linked-listpseudocode

Finding the last K in a singly linked list


I have an algorithm that should take input k and return the corresponding k-th last element, so if k=1, it should return the last element, if k=2 if should return the second last element...and so on

I am not understanding what some of the lines of code are doing or why they need to be there such as:

n = n - k + 1

this is the entire code, any help understanding what each line is doing would be great:

function lastk(List L, Int k) → List 
  tmp = L
  n = 0
  while tmp ̸= NIL do
    n=n+1
    tmp = tmp.next 
  if n<k then
    return NIL 
  else
    tmp = L
    n = n − k + 1 
    i=1
    while i < n do
      tmp = tmp.next
      i=i+1 
    return tmp

Solution

  • First while loop calculates the length of the list L returns NIL if this length is less than k.

    Next two lines else tmp = L are redundant.

    n − k + 1 is the index of the k-th element from the end.

    Second while loop traverses the list to this element.