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;
    }
    

Log in to reply
 

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