Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n))


  • 0
    G

    I think we can use "reverse-binary search" method. We using a Stack<Node> indexs to store the Nodes that at at positions 1, 2, 4, 8, 16, 32 ...., and using another stack to reversely print each region.

    | 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | 16 17 18 19 20 21 22 23 24 25

    Thus, the time complexity is O(n), and spaces complexity is maximum at (n/2 + log(n/2)), where (n/2) is used to print the last region, and log(n/2) is used to store the indexes.

    We can also using reverse binary search to print the last region if we want to save more space.


  • 0

    @gschengcong (n/2 + log(n/2)) doesn't fulfill the "less than linear space" requirement, though. So you'd really have to do the extension you mention in the last sentence. What's the space complexity then? Is it O(log2 n)?


  • 0
    W

    Reversing a singly linked list takes O(n).
    It was immutable.


  • 0
    W

    @StefanPochmann I think your idea roots from the so-called "Skip List" https://en.wikipedia.org/wiki/Skip_list


  • -1
    J

    '''
    reverseList(L *list) {
    dummy = new(list)
    dummy.next = L
    cur := L
    for( cur != nil && cur.next != nil ) {
    tmp := cur.next
    next := tmp.next
    tmp.next = dummy.next
    cur.next = next
    dummy.next = tmp
    }
    cur := dummy.next
    for (cur !-nil) {
    fmt.Println(cur.val)
    }


  • 0
    V

    My solution, I think space is log(N):

    def reverse_print(start, end):
        if start == end:
            return
    
        slow = fast = start
        while fast.next != end and fast.next.next != end:
            slow = slow.next
            fast = fast.next.next
    
        reverse_print(slow.next, end)
        print slow.val,
        reverse_print(start, slow)
    
    reverse_print(root, None)
    

  • 0

    @vincewu That's not linear time, though.


  • 0
    V

    @StefanPochmann Yes, time complexity should be NlogN.
    Is there a better way with linear time and constant space?


  • -1
    J

    @vincewu
    My Given solution should do it O(n) with O(1) space .
    Here is Code which written in Go. Logic it iterate list and reverse its pair nodes. i.e 1-2-3 -4
    iter -0: 2-1-3-4 , iter-1 : 3-2-1-4, iter-3: 4-3-2-1

    reverseList(L *list) {
    dummy = new(list)
    dummy.next = L
    cur := L
    for( cur != nil && cur.next != nil ) {
    tmp := cur.next
    next := tmp.next
    tmp.next = dummy.next
    cur.next = next
    dummy.next = tmp
    }
    cur := dummy.next
    for (cur !-nil) {
    fmt.Println(cur.val)
    }


Log in to reply