单链表转置问题

swangwu

原题：
已知一个单链表，要求不增加辅助变量，实现单链表转置，
也就是表尾变表头，表头变表尾。


大家对单链表转置问题，怎么处理的？
我只想出非递归算法，在VC下调试通过。

typedef int Data;

typedef struct Node
{
        Data d;
        Node *next;
}Node;

/********************************************************************
*Name:  
* Node * revert_printf2(Node *h, Node *n);
*Node *h, h is the pointer of previous node
*Node *n, n is the pointer of next node pointed by h->next
*Description:  
*   
*Returns:  
* The pointer of the head node after transpose
********************************************************************/
Node * revert_printf2(Node *h, Node *n)
{
        Node *k, *p, *header;

        h->next = NULL;

        while (NULL !=h && NULL != n)
        {
                k = n->next;
                n->next = h;
                h = n;
                n = k;
        }

        return h;
}

调用的时候，假设head指向头结点

ret = revert_printf2(head, head->next);

ret就是转置后的头结点

crosszhang

递归做法
type struct Node{
...................
} *node;

node reverse(node frist)
  {
      node head, p;

      if(!first || !first->next)  
         return first;

      p = first->next;
      head = reverse(p)
      p->next = first;
      first->next = NULL;

      return head;
  }

lasting007

小弟，最开始没看清题意写了个递归 ,可惜是2个参数的，

Node *reverse(Node *first, Node *bf)
{
   Node *p, *q;

   if(fist == NULL)
   {
      return fist;
   }

   if(fist->next == NULL)
   {
      fist ->next = bf;
      return first;
   }

   p = first->next;
   q = rerverse(first, first->next);
   first->next = bf;
  
   return q;
}

[ 本帖最后由 lasting007 于 2009-12-4 02:05 编辑 ]