LeeCode 206. 反转链表
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//**方法一：迭代**//
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur=head,*pre=NULL;
    while(cur){
        struct ListNode*tempnext=cur->next; /*若令temp=cur，temp->next会随着cur->next改变而改变,因此需要提前存起来的是cur->next而不是cur*/
        cur->next=pre;
        pre=cur;/*pre一定要紧跟cur这样才能令前一结点指向后一个*/
        cur=tempnext;
    }
    return pre;/*若是头结点cur不存在则直接返回NULL*/
}


//**方法二：递归**//
struct ListNode* reverseList(struct ListNode* head){
    if(!head||!head->next) return head;
    struct ListNode*newhead=reverseList(head->next);
    head->next->next=head;
    head->next=NULL;
    return newhead;
 }

从后开始往前递归，递归到最后，最后一个结点是newhead，倒数第二个结点是head，使newhead指向head然后取消head->next的指向newhead,一层一层从后往前递归过程中，改变的是head->next->next和head->next，而newhead一直是最后一个结点没有变！链表变为由最后一项开始往前指，原先的头结点指向NULL。因此返回最后新的头结点