题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：
No.206 反转链表（Easy） - 图1

递归思路

递归函数的功能：

  1. 传入一个结点head，让结点的下一个结点指向该结点；
  2. 让head结点指向Null

因为是递归， 所以步骤是：

  1. 5->4->null
  2. 4->3->null
  3. …
  4. 2->1->null

返回值为新的head

终止条件

head == null || head.next == null

递归代码

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if (head == null || head.next == null) {
  4.             return head;
  5.         }
  7.         ListNode newHead = reverseList(head.next);
  8.         head.next.next = head;
  9.         head.next = null;
  11.         return newHead;
  12.     }
  13. }

非递归思路

双指针迭代

  1. 用pre指向null, head指向head;
  2. 循环，让head指向pre, 并让pre和head都往后指一个结点；
  3. 停止循环时完成了所有反转，返回head即可。

双指针代码

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if (head == null || head.next == null) {
  4.             return head;
  5.         }
  7.         ListNode pre = null;
  9.         while (head != null) {
  10.             ListNode nextNode = head.next;
  11.             head.next = pre;
  12.             pre = head;
  13.             head = nextNode;
  14.         }
  16.            return pre;
  17.     }
  18. }

非常重要的点

在循环开始时，head指向的结点和前一个结点之间是断开的，例如：
当head指向1时，null 和 1之间是断开的，null 1->2->3->4->5
当head指向2时，1和2之间是断开的，null<-1 2->3->4->5
那么当head指向5时，仍然需要再执行一次循环，因此判断条件不能是head.next != null 而是 head != null， 只有当head指向null时，5和4之间才连接起来，即完成了所有的反转。

但是此时head指向null，那么怎么返回5作为新的头结点呢？
我们的pre总是指向head的前一个结点，因此当head指向Null时，pre刚好指向5，即新的头结点，因此最后返回pre即可。

总结

该题采用迭代，比递归更好理解，因此推荐使用迭代。