反转一个单链表。
示例:
输入: 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;
}
中间过程输出
