206. 反转链表
难度简单2766
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入： head = [1,2,3,4,5] 输出： [5,4,3,2,1] 复制代码
示例 2：
输入： head = [1,2] 输出： [2,1] 复制代码
示例 3：
输入： head = [] 输出： [] 复制代码
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路
方法1：递归。
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { if (head == null) return null; // 空链表 if (head.next == null) return head; // 只有一个节点 let newHead = reverseList(head.next); // 指向链表末尾节点 head.next.next = head; // newHead->1->2->3->4->5->null head.next = null; return newHead; }; 复制代码
方法2. 非递归解法 - 头插法：
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { let newHead = null; // 产生新节点 while(head != null) { let temp = head.next; // 记录head.next节点（head 节点不断后移） head.next = newHead; // 链接新节点 newHead = head; // 链接新添加的节点 head = temp; // 更新head节点 } return newHead; // 返回新头结点 };
