1496: 【秋季】CSP完善程序(链表反转)

链表反转 :  下面的两个函数用递归与非递归实现了单向链表的反转。

                 例如:有一个链表是: 1->2->3->4->5 ，反转后成为 5->4->3->2->1。

现给定如下的单向链表定义:

struct Node

{

   int  data;

   Node *next;

};

Node *head=NULL;

非递归实现:

Node *reverseList(Node *head)

{  

     if ( head==NULL || head->next==NULL)

     {  

            return head;

     }

     Node *pre=NULL*cur=head*temp;  

     while(cur!=NULL)

     {

           temp = cur->next;

           ___ (1) ___ = pre;

           pre = cur;

           cur=  ___ (2) ___ ;

     }

     head=pre;

}

递归实现:

Node *Recursive(Node *head)

{

       if (head == NULL || head->next == NULL)

       {

              return head;

       }

       else

       {

              Node *new_head = ___ (3) ___  ;

               ___ (4) ___  = head;

              head->next = ___ (5) ___  ;

             return new_head;

       }

}

供选择的答案:

(1) A. pre->next    B. cur->next    C.head->next    D. NULL

(2) A. cur->next    B. pre->next    C.pre                D. temp

(3) A. Recursive(head->next)    B. Recursive(pre)    C. Recursive(cur)     D. Recursive(head)

(4) A.pre->next->next      B. cur->next->next    C. head->next->next    D. NULL

(5) A.pre->next                B. cur->next             C. head->next              D. NULL