[链表]-206. 反转链表

反转一个单链表。

示例:

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

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

---

解析：

方法一：

因为反转链表头节点会发生变化，定义两个指针p，q，p指针和head指针同步后移，p向前给head挂链。q指针的位置不变，改变的是它的next节点，不断地挂p的next节点直至最后q指向NULL成为最后一个节点。这个方法会耗费很长时间。

迭代：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if( head == NULL || head->next == NULL ) return head;
        struct ListNode *q=NULL;
        struct ListNode *p=NULL;
        q=head;//q不动
        p=head->next;
        while(p){
            q->next=p->next;
            p->next=head;
            head=p;
            p=q->next;
        }
        return head;        
}

方法二：

递归的解法，思路是不断进入递归函数，直到head指向最后一个节点，递归到底，最后一个节点会根据非空条件直接返回至倒数第二个节点，然后进行操作，反向挂链，挂NULL，最后返回p，返回上一层。

第一次 return p
进行操作

struct ListNode* reverseList(struct ListNode* head) {
    if( head == NULL || head->next == NULL ) return head;
    struct ListNode* p =  reverseList(head->next);
    head -> next -> next = head;
    head -> next =  NULL;     
    return p;
}

---

中间过程输出