单链表反转问题

要求，给定一个单链表，要求对改单链表实现反转，即最后一个结点变成头结点

单链表定义和建立：

 1 typedef struct Node
 2 {
 3     int data;
 4     Node * pNext;
 5 }Node,*LinkList;
 6 
 7 void CreateListHead(Node **L, int n)
 8 {
 9     Node* p;
10     int i;
11 
12     *L = (Node*)malloc(sizeof(Node));
13     (*L)->pNext = NULL;
14 
15     for( i=0; i < n; i++ )
16     {
17         p = (Node*)malloc(sizeof(Node));  // 生成新结点
18         p->data = n-i;
19         p->pNext = (*L)->pNext;
20         (*L)->pNext = p;
21     }
22 }

迭代实现思路：

 1 Node* ReverseLink(Node **head)
 2 {
 3     Node *next;
 4     Node *prev = NULL;
 5  
 6     while((*head) != NULL)
 7     {
 8         next = (*head)->pNext;
 9         (*head)->pNext = prev;
10         prev = (*head);
11          (*head) = next;
12      }
13  
14     return prev;
15  }

递归实现：

整个递归中，newhead经过不断递归调用，最终指向到了最后一个结点，也就是我们需要返回的链表的新头结点，然后，head指针在递归完成后，要做回溯工作，即反转方向。因为外层利用了堆栈存下了前面的结点和指向，所以递归完成后，外层一定有一个指针还指着head，这也是递归可以比迭代少用一个变量的原因）

 1 Node *ReverseLink2(Node **head)
 2 {
 3     Node *newHead;
 4 
 5     if((*head)->pNext == NULL)
 6         return (*head);
 7 
 8     newHead = ReverseLink2(&(*head)->pNext); /*递归部分*/
 9     (*head)->pNext->pNext = (*head);         /*回朔部分，把head的下个节点指向自己，head节点指为NULL*/
10     (*head)->pNext = NULL;
11 
12     return newHead;
13 }