反转链表

反转一个单链表。

示例:

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

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

三种方法：1.栈法2.迭代3.递归

栈法：先遍历一遍链表用栈保存然后用栈反向赋值给链表。

迭代：（设计链表算法最好在纸上画出来，再写程序）

设置三个指针，其中pre指向head，cur->next=pre,t在pre前面

遍历直到pre指向NULL,遍历时让pre->next=cur,需要临时指针来完成交换

递归：

class Solution { public: ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) // 空链或只有一个结点，直接返回头指针 { return head; } else // 有两个以上结点 { ListNode *new_head = reverseList(head->next); // 反转以第二个结点为头的子链表 // head->next 此时指向子链表的最后一个结点 // 将之前的头结点放入子链尾 head->next->next = head; head->next = NULL; return new_head; } } };