思路
方法一：迭代 假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
方法二：递归
递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？
复杂度分析
方法一
时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。空间复杂度：O(1)。方法二
时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode cur=head; ListNode pre=null; ListNode next; while(cur!=null) { next=cur.next; cur.next=pre; pre=cur; cur=next; } return pre; } } public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; }
