C++ scratch space 問題

我想問下面段code算唔算係O(1) scratch space...
我有fd話咁樣算係O(n) scratch space...
thx
  1. struct listNode {
  2.     int item;
  3.     listNode* next;
  4. };

  5. typedef listNode* ptr;

  6. void merge(ptr& a, ptr mid, ptr& b) {
  7.    // PRE: a is the first node of the list
  8.    // b is the last node of the list
  9.    // mid is a pointer to an item between a and b such that
  10.    // items between a and mid are sorted, AND items between mid->next and b are sorted.
  11.    // POST: Produces a merge of the list between a and b (items now completely sorted).
  12.    // Uses O(1) scratch space.
  13.    if(a->item>mid->next->item){
  14.       ptr temp=mid->next;
  15.       ptr end=b;
  16.       mid->next=mid->next->next;
  17.       temp->next=a;
  18.       a=temp;
  19.       if((a->next==mid && a!=end)||(a->next!=mid && a!=end))
  20.          merge(a->next,mid,b);
  21.       else
  22.          b=mid;
  23.    }
  24.    else if(a!=mid)
  25.       merge(a->next,mid,b);
  26.    // Complete the code.
  27. }
複製代碼

[ 本帖最後由 bunch 於 2009-3-21 18:33 編輯 ]