107 lines
2.4 KiB
JavaScript
107 lines
2.4 KiB
JavaScript
/*
|
||
删除排序链表中的重复元素（LeetCode83）206. 反转链表
|
||
简单
|
||
|
||
相关标签
|
||
相关企业
|
||
给你单链表的头节点 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
|
||
*/
|
||
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* function ListNode(val, next) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.next = (next===undefined ? null : next)
|
||
* }
|
||
*/
|
||
|
||
// 思路1
|
||
// const reverseList = function (head) {
|
||
// if (!head || !head.next) return head; // 如果链表为空或只有一个节点，直接返回
|
||
|
||
// const stack = []; // 创建一个栈
|
||
|
||
// // 遍历链表，将节点依次压入栈中
|
||
// let current = head;
|
||
// while (current !== null) {
|
||
// stack.push(current);
|
||
// current = current.next;
|
||
// }
|
||
|
||
// const newHead = stack.pop(); // 取出栈顶节点作为新链表的头节点
|
||
// let newCurrent = newHead;
|
||
|
||
// // 依次弹出栈中的节点，连接成新的链表
|
||
// while (stack.length > 0) {
|
||
// newCurrent.next = stack.pop();
|
||
// newCurrent = newCurrent.next;
|
||
// }
|
||
|
||
// newCurrent.next = null; // 尾节点的 next 指针置空，确保新链表的结束
|
||
|
||
// return newHead; // 返回新链表的头节点
|
||
// };
|
||
|
||
// 思路2 （迭代法）
|
||
|
||
// const reverseList = function(head) {
|
||
// let prev = null;
|
||
// let current = head;
|
||
// while (current !== null) {
|
||
// const nextTemp = current.next;
|
||
// current.next = prev;
|
||
// prev = current;
|
||
// current = nextTemp;
|
||
// }
|
||
// return prev;
|
||
// };
|
||
|
||
// 思路3 （递归法）
|
||
import { LinkListNode as ListNode } from '../../list/index.js';
|
||
|
||
const reverseList = function (head) {
|
||
if (head == null || head.next === null) return head;
|
||
const rList = reverseList(head.next);
|
||
head.next.next = head;
|
||
head.next = null;
|
||
return rList;
|
||
};
|
||
// 示例链表：1 -> 2 -> 3 -> 4 -> 5
|
||
const node1 = new ListNode(1);
|
||
const node2 = new ListNode(2);
|
||
const node3 = new ListNode(3);
|
||
const node4 = new ListNode(4);
|
||
const node5 = new ListNode(5);
|
||
node1.next = node2;
|
||
node2.next = node3;
|
||
node3.next = node4;
|
||
node4.next = node5;
|
||
|
||
// 反转链表
|
||
const reversedHead = reverseList(node1);
|
||
|
||
// 打印反转后的链表
|
||
let current = reversedHead;
|
||
while (current !== null) {
|
||
console.log(current.val);
|
||
current = current.next;
|
||
}
|