Thursday, July 17, 2008

mth to last element in a linked list

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