题目描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0 ≤ n ≤1000

要求

空间复杂度 O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
在这里插入图片描述

输出样例

示例1：
输入：{1,2,3}
返回值：{3,2,1}

实例2：
输入：{}
返回值：{}
说明：空链表则输出空

解决问题的思路

对于数据结构的题，最好还是一边画图一边思考问题。这个题我简单画了一下图，如下：
在这里插入图片描述
图画的不是很好，大家凑合着看一下吧，画图可以为我们提供方很多思路，看着这张图，我们就可以知道这个题的目的就是让我们改变链表每个节点的指向
这个题就很简单了，用头插法就可以解决这个问题。
我们可以先找到第二结点，然后把从第二个结点开始之后的结点依次用头插法放在第一个结点的前面。
其实在这里有一个问题需要大家注意一下，就是我用头插法插完之后，不能直接把指针域给改变了，否则就会找不到下一个节点了。看下图：
在这里插入图片描述
链表本身就只是逻辑上的连续，靠着指针域找到下一个结点。这里将第二个结点放在头结点后，如果将它的指针域修改之后，它就与后面的结点断开了联系，就找不到后面的结点了。在这里看上去不是特别明显，只有三个结点，但如果是很多个结点，那么就会丢掉很多个结点。
要解决这个问题也很简单，只要我们每次把要进行头插的结点和它的下一个节点都存下来就没问题了。
当然数据结构是一门逻辑非常严谨的学科，在实例2中给了空链表的问题，如果没有给我们空链表实例我们也要考虑到。不只有空链表，还有只有一个结点的链表的这种情况，只有一个结点那就不需要反转了，直接返回这个结点就可以了。

代码实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //空链表
        if(head == null){
            return null;
        }
        //结点只有一个
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}