反转链表

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

思路

pHead为当前结点，如果当前结点为空的话，直接返回； pHead为当前结点，pre为当前结点的前一个结点，next为当前结点的下一个结点； 需要完成的目标是将pre–>pHead–>next1–>next2–>··· ···–>end反转为pre<–pHead<–next1<–next2<–··· ···<–end； pre结点可以用来反转方向，为了避免反转之后链表断开，用next结点暂时保存next1结点； 先用next保存pHead的下一个结点信息，保证单链表不会断裂； 保存之后，让pHead从指向next变成指向pre； 到此，完成了pre到pHead的反转，即pre<–pHead; 将pre，pHead，next依次向后移动一个结点。 循环操作，直到pHead为null，此时pre就是链表的最后一个结点，链表反转完毕，pre为反转后链表的第一个结点。 输出pre就是反转之后所得的链表。

代码

/*function ListNode(x){ this.val = x; this.next = null; }*/ function isEmptyObject(obj) { for (var name in obj) { return false; } return true; } function ReverseList(pHead) { if (isEmptyObject(pHead)) { return false; } var pre = null; var next = null; while (pHead != null) { next = pHead.next; pHead.next = pre; pre = pHead; pHead = next; } return pre; } }

拓展

利用递归实现反转

思路

递归的基线条件：遍历到末节点（node.next === null） 递归的递归条件：node.next !== null 当遇到末节点时，返回末节点，前一节点接收末节点，并把末节点的next设置为自身，返回前一节的，继续下去 考虑特殊情况：undefined和null

var reverseList = function (head) { // 闭包 if (head === undefined || head === null) return null var originalHead = head var reverseHead var reverse = function (head) { if (head.next === null) { reverseHead = head return head } else { var node = reverse(head.next) node.next = head if (originalHead === head) { head.next = null return reverseHead } else { return head } } } return reverse(head) };