题目描述
- 题目地址：http://mtw.so/6jyXMj
- 题目要求
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：0≤n≤1000
要求：空间复杂度O(1) ，时间复杂度 O(n) 。
- 题目示例
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1
输入：{1,2,3}
输出：{3,2,1}
示例2
输入：{ }
返回值：{ }
说明：空链表则输出空
解题思路
- 我们要注意边界条件处理：
链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？ - 需要创建两个指针p1和p2,p1用来记录当前链表pHead 后面的链表，p2 指针用来创建新的反转链表。
解题代码
function ReverseList(pHead){
if(pHead == null || pHead.next == null){ // 判断链表为空或长度为1的情况
return pHead;
}
let p1= null,
p2 = null;
while(pHead!=null){
p1= pHead.next // 第一步：指针指向pHead 后面的链表；
pHead.next =p2 // 第二步：记录反转链表的位置
p2 = pHead //第三步：反转链表的位置指向反转链表的新的头节点
pHead = p1 //第四步：将计算链表的pHead.next设置为表头，重新循环
}
return p2
}
module.exports = {
ReverseList : ReverseList
};