题目：反转一个单链表。

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

解题思路：（不带头节点）

1. 当链表为空时，return head;
2. 否则，令结点p = head->next, 然后令head->next = NULL。当p不为空时，用结点q保存p的下一个结点，然后对p进行头插。如此重复，直到p为空。

代码：

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


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *p, *q;

    if(head == NULL )
        return head;
    else
    {
        p = head->next;
        head->next = NULL;
        while(p)
        {
            q = p->next;       //记录下一个结点
            p->next = head;
            head = p;
            p = q;
        }
        return head;
    }
    

}

扩展（其他解法）：

1. 新建一个链表，遍历原链表，将每个结点取下，头插到新链表中。
   代码：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *newhead = NULL, *p;//newhead表示新表的首结点，初始化为NULL.
    while (head){
        p = head -> next;
        head -> next = newhead;
        newhead = head;
        head = p;
    }
    return newhead;
}

2. 递归（待补充）