问题描述：
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。
输入：{1,2,3}
输出：{3,2,1} (若输入空链表则输出空）
以上转换过程如下图所示：
思路分析：
-
采用头插法。从链表的第二个节点开始依次进行头插，直到下一个元素为null时返回head。
-
首先定义一个cur来表示链表的第二个节点，即cur = head.next。
-
然后将head指向的元素地址置为空，因为反转之后head将是最后一个元素。即head.next = null。
-
因为要对每个节点都要进行头插，因此需要遍历整个链表，即循环条件就是当cur为空时遍历结束。
-
根据头插法原理，让cur指向head，即cur.next = head。然后新的头节点就是cur，即head = cur。
-
因为头插法会修改cur的指向，即需要再定义一个节点在修改cur.next前用来保存cur的下一个节点，每次头插结束，让cur等于下一个节点，进行下一次的头插。
-
最后还应考虑到两种特殊情况：当head为空时，直接返回null；当只有一个节点时，直接返回head。
代码展示：
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;
}