题目

输入一个链表，反转链表后，输出新链表的表头。

方法

参考：https://www.nowcoder.com/profile/980167/codeBookDetail?submissionId=1523199
时间复杂度：n

思路

非递归与递归两种办法
非递归就是遍历，按顺序修改节点的next指向；
这里阐述递归的写法，递归方法通过递归走到next的末端，获取到末尾节点作为newhead，将newhead返回。
对每个节点都递归调用，先把当前节点后的链表反转，也就是p.next反转完，再将p和p.next的指向修改为p.next指向p，最后仍然返回newhead

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead) {
  // write code here
  if (!pHead || !pHead.next) return pHead
  let reversePHead = ReverseList(pHead.next)
  pHead.next.next = pHead
  pHead.next = null
  return reversePHead
}