-1
$\begingroup$


I have a linked list with n elements and my goal is to find the 'nth to last element' in the list. I would like to present my approach. Please provide your opinions on whether it is optimal or how may I improve it.
Sample linked list "4->5->6->8->2->9->1"
Suppose the question indicates find 3th to last element in the list.

a)In a single pass, get the length of the linked list
b) Determine which node needs to be traversed upto (len(list)-nth element from last-1)
c) Make (len(list)-nth element from last-1) moves from head to get the element

Run time should be O(n)
Thank you

$\endgroup$
  • 2
    $\begingroup$ I assume everybody understands, but still: speaking about n elements and 'nth to last' element is a bit imprecise. Rather ask about 'kth to last' $\endgroup$ – tevemadar Oct 17 '17 at 20:22
  • 2
    $\begingroup$ @tevemadar Imprecise, or an easy problem. $\endgroup$ – Raphael Oct 17 '17 at 20:32
1
$\begingroup$

tevemadar's solution is the standard double-runner/pointer method. I'll offer up a little different solution because I think it's interesting. It is a similar approach that utilizes sufficiently less "reads" if $n \gg k$.

We will do this by keeping track of a well positioned "checkpoint". Checkpoint c1 will always be $k$ nodes behind checkpoint c2. Checkpoint c2 will always be $< k$ nodes behind our runner a. If we ever iterate a less than $k$ nodes past c2 before hitting the end, we can restart at our checkpoint c1.

func(list L, int k):
  let n = 0
  let a = c1 = c2 = L.head

  do k times: a = a.next
  let c2 = a

  i = k
  while i == k:
    i = 0
    do k times or until a = null:
      i = i + 1
      a = a.next
    if i == k:
      c1 = c2
      c2 = a
    else: break
  a = c1
  do i times: a = a.next
  return a

You read the head node once, then $n$ nodes with your a iterator, then at most $k-1$ more times after going back to your check point. So this is $n + k$ reads total if you only consider node.next to be reads. Compared to the ordinary double runner method which would be $2n - k$ reads. Asymptotically there is no difference though. You can do the other operations you describe pretty trivially with some extra variables and pointer manipulation.

$\endgroup$
0
$\begingroup$

The length of list is not needed in my opinion, I would traverse the list using two iterators, k nodes apart:

1) run iterator 'a' to kth element
2) start iterator 'b' from head
3) proceed iterator 'a' to the end of list, stepping 'b' each time when you step 'a'
end) 'a' arrives to last element, 'b' arrives to 'kth to last' at the same time.

Of course you can also count indices in the process, for getting the length of list.

$\endgroup$
0
$\begingroup$

I think the best option is (in C):

void printFromElementIndex(int elementIdx, struct list* p){
    int idx = 0;
    while(p->next != NULL){       
        // if the n(th) element is reached we print
        if(idx >= elementIdx)
            printf ("%d ->", p->k);

        // we go to the next element on the list
        idx++;
        p = p->next;
    }
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.