反转链表-js

题目
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

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

双指针法

1. 定义一个cur指针指向头结点
2. 定义一个pre指针为空
3. 首先将cur的next存给临时变量temp
4. 将cur的指向反转，即将cur指针指向pre
5. 将pre和cur指针都往后移一位，pre=cur，cur=temp
6. 循环执行3到5，当pre移动到链表的尾部，此时cur为null ,即结束循环
7. 返回pre
   

function ReverseList(pHead)
{
    // write code here
    let pre = null
    let cur = pHead
    while(cur){
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
}
module.exports = {
    ReverseList : ReverseList
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递归法

1. 定义一个反转函数reverse
2. 函数终止条件是cur为null

function reverse(pre,cur){
    if(cur == null){
        return pre
    }
    let temp = cur.next
    cur.next = pre
    return reverse(cur,temp)
}
function ReverseList(pHead)
{
    // write code here
    
    return reverse(null,pHead)
}
module.exports = {
    ReverseList : ReverseList
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17