# NC78 反转链表

# 算法思路：

这道题目主要思想是使用虚拟头节点进行翻转，注意next的指针的保存，如果不保存next指针，翻转之后就找不到next了。

入参pHead是一个链表，假设为 1 -> 2 -> 3 ->null, 使用代码块来描述：

pHead : ListNode { val: 1，next: ListNode }
  -> next: ListNode { val :2 next: ListNode }
    -> next: ListNode { val :3 next: null }

第一轮循环，各个变量的值分别是：
cur: ListNode {val: 2, next: ListNode}
pHead: ListNode {val: 1, next: null}
pre: ListNode {val: 1, next: null}
next: ListNode {val: 2, next: ListNode}

第二轮循环，各个变量的值分别是：
cur: ListNode {val: 3, next: null}
pHead: ListNode {val: 1, next: null}
pre: ListNode {val: 2, next: ListNode}
next: ListNode {val: 3, next: null}

第三轮循环，各个变量的值分别是：
cur: null
pHead: ListNode {val: 1, next: null}
pre: ListNode {val: 3, next: ListNode}
next: null

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

/*function ListNode(x){
  this.val = x;
  this.next = null;
}*/
function ReverseList(pHead) {
  let pre = null
  // 将pHead赋值给cur，其实是指针赋值给了cur 
  // cur指向变了 pHead 也就是原来的链表指向也变了
  let cur = pHead

  while (cur !== null) {
    // 保存next指针
    let next = cur.next
    // 将当前元素next指向前面新创建的pre
    cur.next = pre
    // 移动pre到cur的位置
    pre = cur
    // 将cur移动到保存的下一个位置
    cur = next
  } 
  // cur为null的时候退出循环，此时pre是cur前一个元素
  return pre
}
module.exports = {
  ReverseList: ReverseList,
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

1027书写练习记录：

1 忘记写判断条件，需要加上, 判空条件
2 while循环的条件写错了，正确的条件应该是 cur !== null 我写成了 cur.next !== null 导致返回值出错
3 为什么返回pre呢？当while循环条件结束的时候，cur肯定为null。pre此时恰好为反转后的链表的头节点。