mthlast(head, m):
if head == null:
throw
if m <= 0:
throw
mthlast = null
node = head
count = 1 // same as m
while node != null:
if count > m:
mthlast = mthlast.next
else if count == m:
mthlast = head
count++
node = node.next
return mthlast
[Hat tip to PIE]
Another way (if the linked list can be traversed only once) is to use circular queue (link) but with O(m) space.
mthlast(head, m):
if head == null:
throw
if m <= 0:
throw
cq = new circular-queue(m)
node = head
while node != null:
cq.enqueue(node)
node = node.next
mthlast = null
if cq.size() == m:
mthlast = cq.peek()
return mthlast
No comments:
Post a Comment