# 题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例 1：

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

tips:

# 解法一：迭代

在遍历节点时，把前一个结点存储起来，当前节点指向前一个结点。

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public ListNode reverseList(ListNode head) {
	if(head == null) return null;
	ListNode cur = head, pre = null, next = null;
	while(cur != null){
	next = cur.next;
	cur.next = pre;
	pre = cur;
	cur = next;
	}
	return pre;
	}
	}

时间复杂度： O (n)，遍历链表一次

空间复杂度：O(1)

主要思路：

递归出口：当前节点为空时

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public ListNode reverseList(ListNode head) {
	return recur(head, null); // 调用递归并返回
	}
	private ListNode recur(ListNode cur, ListNode pre) {
	if (cur == null) return pre; // 终止条件
	ListNode res = recur(cur.next, cur); // 递归后继节点
	cur.next = pre; // 修改节点引用指向
	return res; // 返回反转链表的头节点
	}
	}