Thursday, July 17, 2008

reverse a linked list

linkedlist:
    head, tail
    reverse():
        if head == null || tail == null:
            throw
        n = head
        swap(head, tail)
        before = null
        while n != null:
            after = n.next
            n.next = before
            before = n
            n = after

In O(n) time for n nodes and in-place.

[Hat tip to KR]

No comments:

Post a Comment