前言
在上一篇文章中我们认识了链表结构，了解了如何链表的特点，以及如何创建一个链表对象和遍历链表。
今天我们来看下如何进行反转链表。
题目介绍：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
网络异常，图片无法展示
|
输入： head = [1,2,3,4,5] 输出： [5,4,3,2,1]
示例 2：
输入： head = [] 输出： []
链表类
首先来看下提供的链表类
// 链表类 class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val = val === undefined ? 0 : val; this.next = next === undefined ? null : next; } }
通过分析链表了类ListNode可知这是一个单向链表，只有一个next节点。如果是双向链表，有prev指针、tail指针就简单的不能再简单了。
方案一：利用数组存储每一个节点，然后反向拼接节点
遍历整个链表，将每一个节点都存储上，数组末尾存储的就是最后一个元素。执行反转链表，只需要从数组末尾重新遍历拼接即可~
Up Code ~ 上码~
/** * @method reverseList1 * @description 利用数组存储每一个节点，然后反向拼接节点 * @param head ListNode | null 头结点 * @returns ListNode | null */ function reverseList1(head: ListNode | null): ListNode | null { // 临界点判断 if (head === null) { return head; } // 定义存储所有节点的数组 const allListNodes = []; // 1. 将每一个节点遍历出来，放入数组中 let currentNode: ListNode | null = head; // 取出默认头结点 while (currentNode) { // 将节点放入allListNode中 allListNodes.push(currentNode); // 移动指针，指向下一个节点 currentNode = currentNode.next; } // 2. 反向遍历allListNodes节点，从尾部开始遍历 // 将currentNode指向最新节点 currentNode = allListNodes.pop() ?? null; // 定义最新的头结点 - let newHead: ListNode | null = currentNode; while (currentNode) { // pop出allListNodes数组中的最新节点 const prev = allListNodes.pop() ?? null; // 兼容处理pop()方法出的undefined值 // 构建链接关系，currentNode.next指向现在的prev if (currentNode !== null) { currentNode.next = prev; } // 指针向数组的现在元素移动 currentNode = prev; } while (currentNode); // 直接返回新的头结点 return newHead; }
功能测试：
const head: ListNode = { val: 5, next: { val: 4, next: { val: 3, next: { val: 2, next: { val: 1, next: null, }, }, }, }, }; const newHead = reverseList1(head); console.log(newHead);
网络异常，图片无法展示
|
效果还是非常OK的~
方案二：利用递归拼接节点
function reverseList2(head: ListNode | null): ListNode | null { if (!head || !head.next) return head; const node = reverseList2(head.next); // 将head节点的next.next指向head // 相当于将head在head.next左侧，移动到了head.next的右侧 head.next.next = head; // 断开当前节点与右侧的链接 head.next = null; // 返回node节点 return node; }
重点：将head从head.next的左边移动到head.next的右边
方案三：使用双指针反转链表
/** * @method reverseList3 * @description 反转链表 - 双指针 * @param head ListNode | null 头结点 * @returns ListNode | null */ function reverseList3(head: ListNode | null): ListNode | null { // 临界点判断 if (!head || !head.next) { return head; } // 当前指针，初始化指向head let currentNode: ListNode | null = head; // 定义头节点指针 let newHead: ListNode | null = null; // 如果当前节点存在 while (currentNode) { // 当前节点的next指针 const next: ListNode | null = currentNode.next; // 当前节点.next指向newHead，这样就反转了 currentNode.next = newHead; // 移动newHead指针，指向最新元素 newHead = currentNode; // 移动currentNode指针，移动到之前的下一个元素 currentNode = next; } // 返回头结点 return newHead; }
双指针的妙用
性能比较
还是搞个20W条测试下，看看孰优孰劣~
// 这里head1/head2/head3都是一样的结构，就是遍历名称不一样 console.time('reverseList1'); for (let i = 0; i < 20 * 10000; i++) { const newHead1 = reverseList1(head1); } console.timeEnd('reverseList2'); console.time('reverseList2'); for (let i = 0; i < 20 * 10000; i++) { const newHead2 = reverseList2(head2); } console.timeEnd('reverseList3'); console.time('reverseList3'); for (let i = 0; i < 20 * 10000; i++) { const newHead3 = reverseList3(head3); } console.timeEnd('reverseList3');
上图
网络异常，图片无法展示
|
通过数据可以看出，方案一的双层循环还是比较慢的，方案二的递归和方案三的双指针时间消耗整体是一致的。
