206. 反转链表

题目

现在 leetcode 的改成了图例，准确的转化为数据应该是

1 -> 2 -> 3 -> 4 -> 5 -> null

需要变成

5 -> 4 -> 3 -> 2 -> 1 -> null

解题思路

这道题不像 237. 删除链表中的节点，这个题目是知道输入的数组，所以可以使用双指针的方法，即只需要把两个节点的地址互相 next 就可以了

比如 n -> n + 1，只需要把 n+ 1 的 next 指向 n 即可

所以可以使用双指针遍历这个单链表

如果知道怎么让两个节点互换位置的话，就可以先在题目中先试一下

解题步骤

function reverseList(head: ListNode | null): ListNode | null {
    let p1 = head
    let p2 = null
    while (p1) {
        console.log('p1= ', p1.val)
        console.log('p2= ', p2 && p2.val)
        console.log('------------------')
        p2 = p1 // 先把 p2 的地址变成 p1
        p1 = p1.next // 然后再往后移动一位
    }

    return null
};

得到的结果为

p1=  1
p2=  null
------------------
p1=  2
p2=  1
------------------
p1=  3
p2=  2
------------------
p1=  4
p2=  3
------------------
p1=  5
p2=  4
------------------

上述的打印可以看出这个方法是可行的，因为是双指针的解法，p2 的地址已经指向了 p1,即p2 -> p1，所以 p1 的地址也需要指向 p2，即 p1.next -> p2

但是如果此时直接p1.next = p2的话，下一步的p1 = p1.next就无法继续执行，所以需要一个临时变量来存储，即得到如下的代码

其实 p2 可以说是一个新的对象，每次一 while 循环的时候都会把 p1 的值给 p2

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head
    let p2 = null
    while (p1) {
        const temp = p1.next
        p1.next = p2
        p2 = p1
        p1 = temp
    }
    return p2
}

最后 p1 返回的指向应该是 null，p2 的指向是 5，所以是返回 p2

复杂度分析

时间复杂度: 时间复杂度因为有个 while 循环，所以时间复杂度为 O(n)

空间复杂度: 空间复杂度因为只有一个临时变量 tmp 去存储，所以空间复杂度为 O(1)