题解 | 反转链表

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
function ReverseList( head ) {
    // write code here
    let current = head
    let previous = null // 首部的前一个为空
    while(current !== null){
        let nextCurrent = current.next // 下一个
        current.next = previous // 转变指针
        previous = current // 移动
        current = nextCurrent // 移动
    }
    return previous
}
module.exports = {
    ReverseList : ReverseList
};

题目给的复杂度要求不能新建数组，只能在原数组上操作；且只能循环一次。

对每一个元素来说，都有前和后，previous->current->nextCurrent，且表头的previous是空，表尾的nextCurrent是空。

由此，可以设置三个指针，遍历每一个current，通过将current的next指针指向previous，就可以完成反转。循环的终止条件为current为null。

过程：

null 1 ->2->3

p c n

p <- c n

null<- 1 <- 2 3

p c n