题解 | #反转链表#

假设单链表为如下： 解题思路：使用头插法，遍历链表的同时进行头插。

​ 我们先定义两个指针 cur 和 curNext，cur表示当前遍历位置的节点，curNext表示cur的下一个节点，cur从head开始。

首先将head置为null，代表链表末尾节点的next。 然后从cur开始进行头插，让cur.next = head; head = cur，注意一定要将curNext赋值，不然就会丢失后面的节点。

实现代码：

public ListNode reverseList(ListNode head) {
    if (null == head) return null; // 判断空链表

    ListNode cur = head; // 从head开始
    head = null; // 将head置为null
    while (null != cur) { // 遍历整个链表
        ListNode curNext = cur.next; // 先保存cur后面的子链表
        cur.next = head; // 头插
        head = cur;
        cur = curNext;
    }

    return head;
}

​ 时间复杂度O(N)：N为单链表的长度，需要遍历每个节点一次。

​ 空间复杂度O(1)：使用几个常量大小的临时变量。