算法：反转链表

一、题目描述

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

 二、解题思路

1.迭代法

原始链表中，每个结点的 next 指针都指向后一个结点。反转链表之后，每个结点的 next 指针都指向前一个结点。因此，反转链表需要改变每个结点的 next 指针指向的结点。

由于单链表中的每个结点都只有指向后一个结点的 next 指针，因此需要另外存储前一个结点，在遍历链表的过程中完成反转。

具体做法是，维护两个变量 prev 和 curr 分别表示前一个结点和当前结点，初始时 prev=null，curr=head。改变 curr 的 next 指针指向时，需要先得到其后面一个结点 next，然后令 curr.next 指向 prev，再将 prev 和 curr 都向后移动一步。对于链表中的每个结点进行上述操作，当 curr 变成 null 时，遍历结束，此时完成链表的反转，prev 指向反转后的链表的头结点。

下图为反转链表的例子。对于每个结点，需要将指向后一个结点的 next 指针变成指向前一个结点。虚线表示 next 指针原来的指向。

2.递归法

也可以使用递归的方法反转列表。迭代的方法较简单，递归的方法相对复杂。

对于递归问题，首先需要考虑终止条件。这道题的终止条件是链表为空或者只有 1 个结点，此时不需要反转，直接返回链表即可。

当链表至少有 2 个结点时，首先将除了头结点以外的部分反转，然后改变头结点和头结点后面一个结点的 next 指针的指向。

例如，原始链表为：

1→2→3
到达结点 3 时为递归的终止条件，回到结点 2。

到达结点 2 时，3 已经反转完毕，将 3 的 next 指针变成指向 2，将 2 的 next 指针变成指向 null。此时链表为：

1→2←3
到达结点 1 时，2 和 3 已经反转完毕，将 2 的 next 指针变成指向 1，将 1 的 next 指针变成指向 null。此时链表为：

1←2←3
反转链表结束。

需要注意的是，递归过程中将当前结点的 next 指针变成指向 null 是不可缺少的操作，否则链表中会出现环。

三、题解代码

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