题目概述

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

附上leetcode链接：

点击此处进入leetcode

思路与代码

思路展现

反转链表这个题目的思路非常的巧妙，在此我们先讲迭代法：

迭代法的思路是这样的：

1:首先定义一个cur指针，开始时指向我们的头节点Head，然后开始往下遍历，cur指针的作用是为了记录我们要反转的节点.

2:其次是定义我们的prev指针，这个指针用于记录当前需要反转的节点的前驱.

3:接下来定义我们的curNext指针，这个指针用于保存下一个要反转的节点.

4:最后定义newHead指针，用于存储反转后的链表的头节点.

反转链表的核心语句一共是四步：

(1):首先我们保存下一个要反转的节点,因为我们如果不保存的话,prev的初始值为null,当执行完cur.next=prev后，此时相当于链表此时只有一个节点了，那么下一个要反转的节点就丢失了，为了避免这种情况的发生，每次反转前都需要拿curNext指针来保存下一个要反转的节点.即curNext=cur.next

(2):保存完毕后，其次是执行语句cur.next=prev,既然是反转链表，说明被反转的节点的next域存储的就是其之前的前驱节点的地址.

当然在执行cur.next=prev前还需要对curNext这个指针进行非空判断，如果为空，说明有两种情况：

情况1：说明此时链表内部只有一个节点，那么反转后还是原先的节点，所以直接将cur赋值给newHead进行返回.

情况2:说明此时cur指针已经遍历到最后一个节点了，最后一个节点就是我们反转后的新链表的头节点，那么可以直接将当前cur赋值给newHead进行返回.

(3):使用prev保存每次被反转的节点，原因是每次被反转的节点都会成为下一个被反转的节点的后继节点,为了以防下一个被反转的节点找不到他的后继节点(这个后继节点之前是下一个被反转节点在反转前的前驱节点)，所以每次都会去保存被反转的节点.

(4):反转后cur就继续往下遍历.注意此处的遍历语句为cur=curNext;并不能写成cur=cur.next.

代码示例

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        ListNode newHead = null;
        if (head == null) {
            return null;
        }
        while (cur != null) {
            ListNode curNext = cur.next;
            if (curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
}

总结

迭代法是最常用的一个办法，其时间复杂度为O(N）,因为最坏的情况下需要遍历一遍链表才能结束(假设链表有N个节点),空间复杂度为O(1).

当然还有一种方法是递归法，理解起来比较难，大家有兴趣可以去leetcode官方去自行查看代码和解析.