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


  • 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)
    }


  • 0
    C

    O(sqrt(n)) space complexity and O(n) time complexity solution:
    It is inspired by the fact that sqrt(n) * sqrt(n) = n and the "reverse words in a sentence" problem

    void reverse(ListNode* begin) {
      int n = 0;
      auto ptr = begin;
      while (ptr) {
        ++n;
        ptr = ptr -> next;
      }
      int k = ceil(sqrt(n));
      vector<ListNode*> tmp1(k, NULL), tmp2(k, NULL);
      int i = 0;
      ptr = begin;
      while (ptr) {
        tmp1[i] = ptr;
        ++i;
        for (int j = 0; j < k && ptr; ++j, ptr = ptr -> next)
          ;
      }
      i = tmp1.size() - 1;
      while (i >= 0 && tmp1[i] == NULL)
        --i;
      if (i < 0)
        return;
      while (i >= 0) {
        auto p = tmp1[i];
        for (int j = 0; j < k && p; ++j, p = p -> next)
          tmp2[j] = p;
        for (int j = k - 1; j >= 0; --j) {
          if (tmp2[j]) {
    	cout << tmp2[j] -> val << " ";
          }
        }
        for (int j = 0; j < k; ++j) {
          tmp2[j] = NULL;
        }
        --i;
      }
      cout << endl;
    }
    

  • 0
    A

    EDIT: this is in fact O(nlogn) time and O(logn) space, as discussed earlier in the thread.

    O(n) O(nlogn) time and O(log n) space solution:

    • Start at the beginning of the list with n (== size of list) to go.
    • Each step store the current head and advance half the distance (n/2)
    • Then print (recursively) that right half, and then the left half, effectively doing the reversal
    • Handle odd ns by printing the midpoint element in between the left and right halves
    • No overlap between calls / prints, therefore O(n) time as mentioned earlier in the thread, recursion is T(n) = n/2 + 2T(n/2) = O(nlogn)
    • At the max depth you'll have logn recursive calls, therefore O(logn) space
    public static void printImmutableListReverse(LLNode l) {
            if (l == null)
                return;
            if (l.next() == null) {
                System.out.println(l.elem() + " -> ||");
                return;
            }
            int n = 0;
            LLNode curr = l;
            while (curr != null) {
                n++;
                curr = curr.next();
            }
            printImmutableListReverse(l, n);
            System.out.println("||");
        }
    
        private static void printImmutableListReverse(LLNode l, int n) {
            if (n == 0) {
                return;
            }
            if (n == 1) {
                System.out.print(l.elem() + " -> ");
            } else {
                LLNode half = l;
                LLNode oddMid = null;
                for (int i = 0; i < n / 2; i++) {
                    half = half.next();
                }
                if (n % 2 == 1) {
                    oddMid = half;
                    half = half.next();
                }
                printImmutableListReverse(half, n / 2);
                if (oddMid != null) {
                    System.out.print(oddMid.elem() + " -> ");
                }
                printImmutableListReverse(l, n / 2);
            }
        }
    

  • 0

    @ariel Max depth of recursion doesn't cut it. The entire recursive call stack counts towards that space, which is about O(n). You are taking up linear amount of space.

    EDIT: Sorry, my bad. Look at comments below.


  • 0
    A

    @babhishek21 I think you're incorrect. The max depth of the recursive call is exactly the size of the call stack, and therefore the space the algorithm takes up. At any given moment you will not have more than log(n) calls on the stack, each taking up constant space, therefore O(logn) space.


  • 0

    @babhishek21 Funny that you go against the correct O(log n) space claim but not against the wrong O(n) time claim :-)

    @ariel You put quite some effort into an approach already shown to be wrong in the first few posts of this thread...


  • 0
    A

    @StefanPochmann Indeed, missed that (was heading on the problem and prematurely posting before exhausting the discussion). Edited original comment with correction.


  • 0

    @ariel Ah, right. Of course it's good to solve on your own first, and that's what takes the most effort. I didn't think that through, probably because I always read other people's solutions after writing my own and before potentially posting mine.

    Still wishing this would become a real LeetCode problem, then I'd write up my own idea that I think is nice, but I guess that won't happen anymore now that LeetCode only does contest problems and because this problem is not suited well for contests...


  • 0

    @StefanPochmann Shoot. My bad. The space complexity is something I'm more interested with, since a O(n) or longer runtime is guaranteed (since it takes O(n) to just find out the length of the list). Did not think about looking that way.
    @ariel You are right, the space requirement is indeed O(logn). My bad.


  • 0

    @StefanPochmann Ask @1337c0d3r to let you put this in. I'm sure this was asked in some interview by someone on Earth.


  • 1

    @StefanPochmann No, this is not true. We still want to add more interesting problems like this that are not suited well for contests.

    Let's work together to publish this problem, shall we? :)


  • 0

    @1337c0d3r Oh, sorry, it's just that I think I haven't seen non-contest problems in a long time. I should work on other stuff, not leetcode, but I guess I can help a bit.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.