Re:Nth-to-Last Element in a Singly Linked List
by basman on Sunday January 31, 2010 @02:06PM
(#1090876)
That's a neat one. My solution: pointers A, B, and C. A proceeds through the list. B is always at the largest multiple of k that is at or before A. C is at B-k. Every k steps, set C=B and B=A. When A reaches the end, step C forward B-A times.
Re:Nth-to-Last Element in a Singly Linked List
by cperciva on Sunday January 31, 2010 @02:29PM
(#1090927)
Yep, that's it. I like this puzzle because while there are lots of examples where having 2 pointers is better than 1, it's the only (non-contrived) example I can think of where 1 point is just as good as 2, but 3 pointers is much better.
Re:Nth-to-Last Element in a Singly Linked List
by extension on Sunday January 31, 2010 @06:23PM
(#1091311)
Neato.
If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer.
Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.
Re:Nth-to-Last Element in a Singly Linked List
by cperciva on Sunday January 31, 2010 @06:37PM
(#1091329)
That doesn't help significantly, since you only save the final O(k) dereferences. The situation (small k) where it's practical to allocate a ring buffer like this is exactly the situation where it isn't useful.
Re:Nth-to-Last Element in a Singly Linked List
by extension on Sunday January 31, 2010 @08:02PM
(#1091474)
Actually, you're right, it's the larger values of k where this might make a difference. If the list items are scattered in memory, the cost of the buffer increases very slowly with k compared to the cost of hitting those extra k/2 items.
Re:Nth-to-Last Element in a Singly Linked List
by caf on Sunday January 31, 2010 @08:35PM
(#1091528)
Your "every k steps" operation executes N / k times, which isn't O(k) so I don't think it meets the requirements given.
Re:Nth-to-Last Element in a Singly Linked List
by cperciva on Sunday January 31, 2010 @08:40PM
(#1091537)
His "every k steps" operation doesn't dereference any pointers; 0 * N / k is indeed O(k).
Re:Nth-to-Last Element in a Singly Linked List
by caf on Sunday January 31, 2010 @08:51PM
(#1091564)
Fair enough, reading comprehension fail.
Re:Nth-to-Last Element in a Singly Linked List
by DenisM on Sunday January 31, 2010 @02:11PM
(#1090891)
It's not equally inefficient. The former will trash the CPU cache on large lists, whereas the latter will not if the k is small.
Re:Nth-to-Last Element in a Singly Linked List
by cperciva on Sunday January 31, 2010 @02:32PM
(#1090934)
True. But the author hadn't gotten to the point of counting operations yet, so I don't think he was trying to make a subtle point about memory hierarchies and non-constant access times. :-)
Re:Nth-to-Last Element in a Singly Linked List
by rabidgnat on Monday February 01, 2010 @12:03AM
(#1091828)
The way I thought of immediately uses 0 pointers:
(defun nthFromEnd (lst n)
(labels ((from-end-helper (lst n)
(if (null lst)
0
(let ((ret (from-end-helper (cdr lst) n)))
(if (eq ret n)
(throw 'answer (car lst))
(+ ret 1))))))
(catch 'answer
(when (from-end-helper lst n)
nil))))
CL-USER> (nthfromend '(1 2 3 4 5) 6)
NIL
CL-USER> (nthfromend '(1 2 3 4 5) 3)
2
CL-USER> (nthfromend '(1 2 3 4 5) 0)
5
I didn't hammer it very hard so maybe I missed a case or two. The other obvious problem is that it's not tail recursive (nor very elegant in general)
Re:Nth-to-Last Element in a Singly Linked List
by liamk on Sunday January 31, 2010 @11:05PM
(#1091752)
What about going through the list once, put each node onto a stack, then pop n - 1 elements off the stack, and the nth last element will be on the top of the stack.
Edit: uses too many pointers as cperciva points out below.
Re:Nth-to-Last Element in a Singly Linked List
by cperciva on Sunday January 31, 2010 @11:17PM
(#1091765)
That uses N additional memory locations, not 3.
Re:Nth-to-Last Element in a Singly Linked List
by andrewcooke on Sunday January 31, 2010 @02:11PM
(#1090889)
heh. thanks for that comment. i had to sit and think for a moment.
Challenge: Show how, using three pointers, you can find the kth last element from a linked list of unknown length N with no more than N + O(k) pointer dereferences.