翻转链表

链表原来的顺序{1,2,3}

按照{3,2,1}打印输出

方法一： 

①定义一个当前节点 cur;定义当前节点的前一个节点 pre ; 定义一个用于保存当前节点后一个节点的临时节点 temp

② temp保存cur->next;  断开当前节点与后一个节点的连接，指向前一个节点 cur->next=pre;  完成一次转向

③ 切换到下一个结点 :当前节点cur变成了前一个节点(pre=cur)，当前节点的后一个节点变成了当前节点(cur=temp)

代码实现：

ListNode * ReserveListNode(ListNode *pHead)

　　if(pHead==Null || pHead->next==Null)

　　　　return pHead;

　　ListNode * cur,*temp,*pre;

　　cur=pHead;

　　while(cur!=NULL)

　　　　temp=cur->next;

　　　　cur->next=pre;

　　　　pre=cur;

　　　　cur=temp;

　　return pre;

 时间复杂度O（n）

空间复杂度O(1)

方法二：

用递归来写。每一个单一节点的翻转可以看成一个递归函数调用

终止条件是 找到最后一个节点

实现代码：

ListNode * ResevreListNode(ListNode* pHead);

       //终止条件  找到链表的尾部

　　if(pHead==Null || pHead->next==Null)

　　　　return pHead;

　　else

　　　　ListNode * newHead=ResevreListNode(pHead->next);//调用递归

　　　　pHead->next->next=pHead;  //到一个节点指向倒二个节点，链表翻转

　　　　pHead->next=Null;//原本的倒二个几点会变成最后一个节点 指向空   其实等于新建了一条链表，然后往里添加元素

　　　　return newHead;

 时间复杂度O(n)

空间复杂度O(n)