一、概念
链表由一组零散的结点通过指针连接而成,每个结点都包含当前结点内容和后继指针。相对于数组,它不受固于存储空间的限制,可更快捷地进行插入和删除操作,主要有以下几种类型:
1、单链表
指针指向下一个节点,终点指向null
2、双链表
指针指向前一个节点和后一个节点
3、循环链表
最后一个节点指向第一个节点
在解决链表相关问题时,先执行三步骤,再敲下代码会更清晰
不同于数组,JS官方还没有提供一个直接的链表API,可通过对象的方式模拟出链表,其结构为
const head = {
data: 1,
next: {
data: 2,
next: null,
},
};
二、leetcode 最常见相关题型
1、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
示例:
输入: l1 = [1,2,4], l2 = [1,3,4]
输出: [1,1,2,3,4,4]
步骤:
var mergeTwoLists = function(l1, l2) {
if (l1 === null) {
return l2
} else if (l2 === null) {
return l1
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l2.next, l1)
return l2
}
};
2、环形链表
给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。如果链表中存在环,返回 true 否则返回 false 。要求用 O(1) 内存解决此问题
pos 表示链表尾连接到链表中的位置,若 pos 是 -1 则该链表中没有环
示例:
输入:head = [3,2,0,-4], pos = 1
输出:true // 链表中有一个环,其尾部连接到第二个节点
步骤:
var hasCycle = function(head) {
if(!head || !head.next) return false;
let slow = head.next;
let fast = head.next.next;
while(slow !== fast ) {
if(!fast || !fast.next) return false;
slow = slow.next;
fast = fast.next.next;
}
return true
}
3、反转链表
给你单链表的头节点 head ,请你使用迭代或递归地反转链表,并返回反转后的链表
示例:
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
步骤:
var reverseList = function(head) {
if(!head || !head.next) return head;
let prev = null;
let cur = head;
while(cur) {
const curNext = cur.next;
// 反转后赋值给prev指针
cur.next = prev;
prev = cur;
// 链接到下一个节点
cur = curNext;
}
return prev
};
4、链表的中间结点
给定一个头结点为 head 的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点(给定链表的结点数介于 1 和 100 之间)
示例:
输入: [1,2,3,4,5]
输出: 3
输入: [1,2,3,4,5,6]
输出: 4
步骤:
var middleNode = function(head) {
if(!head || !head.next) return head;
let slow = head;
let fast = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow
};
5、删除链表倒数第 n 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点
示例:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
步骤:
const removeNthFromEnd = function (head, n) {
// 哨兵
let preHead = new ListNode(0)
preHead.next = head
let slow = preHead;
let fast = preHead;
// 先走n步
while (n--) {
fast = fast.next
}
// 一起走
while (fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return preHead.next;
};
6、回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false
示例:
输入: head = [1,2,2,1]
输出: true
步骤:
var isPalindrome = function (head) {
const res = []
while (head) {
res.push(head.val);
head = head.next
}
let pre = 0;
let last = res.length - 1;
while (pre < last) {
if (res[pre] !== res[last]) return false;
pre++;
last--;
}
return true
}
8、相交链表
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。题目数据保证整个链式结构中不存在环。
注意:
示例:
输入:intersectVal = 4, listA = [1,2,3,4,5], listB = [6,7,4,5], skipA = 3, skipB = 2 // 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 2 个节点
输出:Intersected at '4' // 相交节点的值为 4 (注意,如果两个链表相交则不能为 0)
步骤:
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = pA !== null ? pA.next : headB;
pB = pB !== null ? pB.next : headA;
}
return pA;
}
9、链表求和
给定两个用链表表示的整数,每个节点包含一个数位,这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果
示例:
输 :(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
步骤:
const addTwoNumbers = function (l1, l2) {
// 哨兵
let preHead = new ListNode(0)
let carry = 0;
let pre = preHead;
while (l1 || l2) {
let sum = 0;
if (l1) {
sum += l1.val
l1 = l1.next
}
if (l2) {
sum += l2.val
l2 = l2.next
}
sum += carry
carry = Math.floor(sum / 10)
pre.next = new ListNode(sum % 10)
pre = pre.next
}
if (carry > 0) {
pre.next = new ListNode(carry)
pre = pre.next
}
return preHead.next
}
进阶:思考 下,假设这些数位是正向存放的, 该如何解决呢?
输 :(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
更新时间:2024-08-18
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号