反转链表

题目描述

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

思路

反转链表，即是如下操作：

准备三个指针：pLeft、pMid和pRight，分别先指向链表的前三个节点，如下

接着，我们只需让pLeft的next指向null,pMid的next指向pLeft,pRight的next指向pMid,并且依次将三个指针同时向前移动，边移动边调整三个指针的next指向，直到pRight为null时，此时pMid为链表的最后一个结点，然后让pMid的next指向pLeft，如下：

而pMid也就是反转后链表的头结点，最终将pMid返回即可。

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead) {
  if (!pHead) {
    return null;
  }
  // 如果传入的链表只有一个元素，那就将原链表返回
  if (!pHead.next) {
    return pHead;
  }
  // 准备三个指针
  let pLeft = pHead;
  let pMid = pHead.next;
  let pRight = pMid.next;

  pLeft.next = null;
  while (pRight) {
    pMid.next = pLeft;
    // 依次向前移动三个指针
    pLeft = pMid;
    pMid = pRight;
    pRight = pRight.next;
  }
  pMid.next = pLeft;
  return pMid;
}