当前位置：网站首页>【LeetCode】Summary of linked list problems
【LeetCode】Summary of linked list problems
2022-08-11 07:51:00 【Peter Pan China】
【LeetCode】List answer key summary
写在前面
这里是小飞侠Pan🥳,立志成为一名优秀的前端程序媛！！！
本篇文章同时收录于我的github前端笔记仓库中,持续更新中,欢迎star~
https://github.com/mengqiuleo/myNote
2. 两数相加
给你两个 非空 的链表,表示两个非负的整数.它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字.
请你将两个数相加,并以相同形式返回一个表示和的链表.
你可以假设除了数字 0 之外,这两个数都不会以 0 开头.
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
题解思路
- The title given number right is high,List starting with low
- We count on when the paper,是从低位开始,Also happens to conform to the list at the beginning of is low
- 所以,首先我们需要一个curryVariable stores carry
- If the current position does not exist,用0补充
- We use a new linked list storage calculated results
var addTwoNumbers = function(l1, l2) {
let curry = 0;//存储进位
let pre = cur = new ListNode(0);
while(curry || l1 || l2){
let val1 = l1 !== null ? l1.val : 0;
let val2 = l2 !== null ? l2.val : 0;
let sum = val1 + val2 + curry;
curry = sum >= 10 ? 1 : 0;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if(l1) l1 = l1.next;
if(l2) l2 = l2.next;
}
return pre.next;
};
19. 删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点.
题解思路
Assume that sets the double pointer p 和 q 的话,当 q 指向末尾的 NULL,p 与 q 之间相隔的元素个数为 n 时,那么删除掉 p 的下一个指针就完成了要求.
- 设置虚拟节点 dummyHead 指向 head
- 设定双指针 p 和 q,初始都指向虚拟节点 dummyHead
- 移动 q,直到 p 与 q 之间相隔的元素个数为 n
- 同时移动 p 与 q,直到 q 指向的为 NULL
- 将 p 的下一个节点指向下下个节点
var removeNthFromEnd = function(head, n) {
let ret = new ListNode(0,head);
let slow = fast = ret;
while(n--) fast = fast.next;
while(fast.next !== null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return ret.next;
};
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的.
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
题解思路
- We customize a node is used to store the new generated list
- When two lists are not traverse up,Smaller value added behind the newly generated list
- Finally the remaining list followed by the
var mergeTwoLists = function(list1, list2) {
let dummy = new ListNode(-1), p = dummy;
while(list1 !== null && list2 !== null){
if(list1.val > list2.val){
p.next = list2;
list2 = list2.next;
} else {
p.next = list1;
list1 = list1.next;
}
p = p.next;
}
if(list1 !== null){
p.next = list1;
}
if(list2 !== null){
p.next = list2;
}
return dummy.next;
};
23. 合并K个升序链表
给你一个链表数组,每个链表都已经按升序排列.
请你将所有链表合并到一个升序链表中,返回合并后的链表.
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到.
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
题解思路
这里使用归并排序
var mergeKLists = function(lists) {
if(!lists.length) return null;
return mergeLists(lists, 0, lists.length - 1);
};
function mergeLists(lists, start, end){
//如果 start === end The end of the show that partition points,只剩一个元素了,直接返回
if(start === end){
return lists[start];
}
//在这里进行：分,Using recursive will list points step by step,直到只剩一个元素
const mid = start + ((end - start) >> 1);
const leftList = mergeLists(lists, start, mid);
const rightList = mergeLists(lists, mid + 1, end);
//调用merge函数：进行合
return merge(leftList, rightList);
}
//合并链表
function merge(head1, head2){
let newHead = new ListNode(0), p = newHead;
while(head1 && head2){
if(head1.val <= head2.val){
p.next = head1;
head1 = head1.next;
} else {
p.next = head2;
head2 = head2.next;
}
p = p.next;
}
p.next = head1 ? head1 : head2;
return newHead.next;
}
24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点.你必须在不修改节点内部的值的情况下完成本题（即,只能进行节点交换）.
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
题解思路
- We first create a virtual noderet,And the virtual head node points tohead
- curTo represent the node is to exchange the second node,preSwapping is the first node
var swapPairs = function(head) {
let dummy = new ListNode(0,head), temp = dummy;
while(temp.next && temp.next.next){
let cur = temp.next.next, pre = temp.next;
pre.next = cur.next;
cur.next = pre;
temp.next = cur;
temp = pre;
}
return dummy.next;
};
25. K 个一组翻转链表
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表.
k 是一个正整数,它的值小于或等于链表的长度.如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序.
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换.
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
题解思路
用栈,我们把 k 个数压入栈中,Then bounced out of order is flip！
这里要注意几个问题：
第一,The rest of the list number is enough k 个（因为不够 k Don't turn over）;
第二,Have to flip the part to connect with the remaining list.
- We set up a virtual head nodedummy,并且还有一个pre指针首先指向dummy
- 然后prePointer will continue to join chain table node in the tail,然后向后移动
- tmp和headFirst nodes are said to join in the stackkA node at the beginning of the
- tmpWill continue to move back,In every move to get the corresponding value add to the stack
- And in each round loop last,都要将headTo mark for the next round ofkThe beginning of the element.
- 将head进行标记,可以保证tmpCorrect traverse each roundk个元素
var reverseKGroup = function(head, k) {
let stack = [];
let dummy = new ListNode(-1, head);
let pre = dummy;
while(true){
let count = 0;
let tmp = head;
while(tmp && count < k){
stack.push(tmp);
tmp = tmp.next;
count++;
}
if(count != k){
//If the rest of the not enough K 个
pre.next = head;//Add the rest of the element at the end of the list
break;
}
while(stack.length > 0){
pre.next = stack.pop();
pre = pre.next;
}
head = tmp;
}
return dummy.next;
};
61. 旋转链表
给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置.
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
题解思路
- The first time cycle for the length of the list
- 长度对k进行取余(长5,移6,The actual shift1)
- 初始化两个指针, When the remainder as the initial interval of two Pointers
- Two pointer move back,When the end right pointer to stop
- Left pointer is end node at this time,The next node is the first
- Pointer to the next node right head pointing to the original node
var rotateRight = function(head, k) {
let dummy = new ListNode(-1, head), pre = dummy;
let len = 0, mod, R = head, L = head;
//First round,求出链表的长度
while(pre.next){
len++;
pre = pre.next;
}
if(len === 0) return dummy.next;
mod = k % len;//The length of the mobile should get real
while(mod--){
R = R.next;
}
while(R.next){
R = R.next;
L = L.next;
}
R.next = dummy.next;
dummy.next = L.next;
L.next = null;
return dummy.next;
};
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 .返回 已排序的链表 .
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
题解思路
- 因为可能删除头结点,So you need to head a virtual nodedummy
- 从dummy节点开始遍历
- 如果当前节点curThe next node and two nodes of the same value,The cycle,将cur节点的next节点设置为cur.next.next
var deleteDuplicates = function(head) {
let dummy = new ListNode(0, head);
let cur = dummy;
while(cur.next && cur.next.next){
if(cur.next.val === cur.next.next.val){
//Adjacent nodes of the same value
let val = cur.next.val;//First to save values
//删除所有值相同的节点
while(cur.next && cur.next.val === val){
cur.next = cur.next.next;
}
} else {
//Value different direct backward traversal is good
cur = cur.next;
}
}
return dummy.next;
};
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 .返回 已排序的链表 .
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
题解思路
- On this topic and the individual difference is：This topic is not delete all the duplicate values,But to keep a
- 所以,We don't need virtual head node at this time,因为头结点head并不会被删除
- If the value of the next node and the current node values are the same,Then the current nodenextSet the node to node after next
var deleteDuplicates = function(head) {
let tmpHead = head;
while(tmpHead !== null){
let next = tmpHead.next;
if(next !== null && next.val === tmpHead.val){
tmpHead.next = next.next;
} else {
tmpHead = tmpHead.next;
}
}
return head;
};
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前.
你应当 保留 两个分区中每个节点的初始相对位置.
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
题解思路
- We use two list,一个smallStore chain table is smaller than the target number,另一个是large链表
- 然后循环head头结点
- 当遍历结束后,在smallThe list followed bylarge链表.并且将largeAt the end of the place0
var partition = function(head, x) {
let small = dummySmall = new ListNode(-1);
let large = dummyLarge = new ListNode(-1);
while(head){
if(head.val < x){
small.next = head;
small = small.next;
}else{
large.next = head;
large = large.next;
}
head = head.next;
}
small.next = dummyLarge.next;
large.next = null;
return dummySmall.next;
};
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right .请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 .
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
题解思路
我们需要两个指针,一个prePointer to point to flip interval before a node,另一个curNode is responsible for the reverse range
整体流程如下：图中的g指针就是pre,p指针(即cur指针)Responsible for traverse the entire reverse range
The above is the whole process,Here we see the realization of the specific list of mobile operator
First of all to flip the first number within the target range
翻转之后
The following is the second time to flip
var reverseBetween = function(head, left, right) {
let dummyNode = new ListNode(-1,head);
let pre = dummyNode;
for(let i = 0; i < left - 1; i++){
//通过循环,To find invert range of a node before
pre = pre.next;
}
let cur = pre.next;//curNode is a fixed value,我们拿到 cur.next And put the node inpre节点的后面
for(let i = left; i < right; i++){
let next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
};
138. 复制带随机指针的链表
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点.
构造这个链表的 深拷贝. 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值.新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态.复制链表中的指针都不应指向原链表中的节点 .
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y .那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y .
返回复制链表的头节点.
用一个由 n 个节点组成的链表来表示输入/输出中的链表.每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数.
random_index：随机指针指向的节点索引（范围从 0 到 n-1）;如果不指向任何节点,则为 null .
你的代码 只 接受原链表的头节点 head 作为传入参数.
题解思路
Refer to the problem solving video：138. 复制带随机指针的链表
首先,To understand the question：
This topic is let's copy the list,And then returns the copy list,But there is a problem：链表有一个random指针,This pointer points to is random,也就是说,May be a noderandomPointer to the behind is not traverse the nodes
Then we can iterate through two times to complete,The first time only copy of the current nodeval值,The second traverse all the nodes copynext,random的节点值.
var copyRandomList = function(head) {
if(!head) return head;
let cur = head;
const map = new Map();
//第一次遍历,生成一个具有valAttribute list
while(cur){
map.set(cur, new Node(cur.val));
cur = cur.next;
}
//第二次遍历,根据map映射关系,将random和nextPointer to the corresponding node ornull
cur = head;
while(cur){
map.get(cur).next = map.get(cur.next) || null;
map.get(cur).random = map.get(cur.random) || null;
cur = cur.next;
}
return map.get(head);
};
141. 环形链表
给你一个链表的头节点 head ,判断链表中是否有环.
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环. 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）.注意：pos 不作为参数进行传递 .仅仅是为了标识链表的实际情况.
如果链表中存在环 ,则返回 true . 否则,返回 false .
题解思路
每次快指针向后移动两个节点,慢指针向后移动一个节点.
如果快指针移动到了链表尾部,就说明链表无环
如果快慢指针相遇了,就说明链表有环
注意：若有环,则快慢指针一定会相遇.因为快指针一定比慢指针提前进入到环中,等慢指针也进入环中后,快指针一定会追上慢指针（因为速度是慢指针的两倍）,并且一定不会不相遇而直接跳过去（慢指针移动前的旧位置和移动后的新位置共22个节点,快指针一次前进22个节点,必定踩上一个）
var hasCycle = function(head) {
if(!head || !head.next) return false;
let slow = head.next, fast = head.next.next;
while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;
if(fast === slow){
// Here the comments section：Is used to calculate the first node,And the next one is for and code to keep consistent with
// slow = head;
// while(fast !== slow){
// fast = fast.next;
// slow = slow.next;
// }
return true;
}
}
return false;
};
142. 环形链表 II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点. 如果链表无环,则返回 null.
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环. 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）.如果 pos 是 -1,则在该链表中没有环.注意：pos 不作为参数进行传递,仅仅是为了标识链表的实际情况.
不允许修改 链表.
题解思路
On this topic and a similarities,Is only the request that we find out the first node of a ring
从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点.
也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2.
让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点.
var detectCycle = function(head) {
if(!head || !head.next) return null;
let slow = head.next, fast = head.next.next;
while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;
if(fast === slow){
// At that moment, we have shown that the existing ring
slow = head; //Defines the two nodes at this time,slowPointer is located in the head start node,fastNode pointer is located in the meet
while(fast !== slow){
//When the two nodes have met,Let the two nodes move back every time a
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
};
143. 重排链表
给定一个单链表 L 的头节点 head ,单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换.
题解思路
- We use an array of first all nodes stored
- Then from the array first and tail（ shift 和 pop ）
var reorderList = function(head) {
if(head === null){
return head;
}
let queue = [];
let p = head
while(p){
queue.push(p);
p = p.next;
}
while(queue.length > 2){
let h = queue.shift();
let t = queue.pop();
t.next = h.next;
h.next = t;
}
queue[queue.length - 1].next = null;//Behind the end node set tonull
return head;
};
147. 对链表进行插入排序
给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 .
插入排序 算法的步骤:
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表.
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入.
重复直到所有输入数据插入完为止.
下面是插入排序算法的一个图形示例.部分排序的列表(黑色)最初只包含列表中的第一个元素.每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中.
对链表进行插入排序.
题解思路
This topic is a linked list insertion sort
- Found to be inserted into the first node（Before a node value is greater than the current）,移除,Remove save before.
- The node is inserted into the right place——From the beginning traverse comparison,并插入.
var insertionSortList = function(head) {
let dummyHead = new ListNode(0,head);
let cur = head;
let prev = null;
let temp = null;
while(cur && cur.next){
if(cur.val <= cur.next.val){
//If the value is growing up
cur = cur.next;
} else{
temp = cur.next;//如果cur.nextThe value is greater than the front,先用temp保存
cur.next = cur.next.next;//此时将temp移出,At the same time to list even after next node
prev = dummyHead;//从头遍历,找到正确的插入位置
while(prev.next.val <= temp.val){
prev = prev.next;
}
//此时prev就是tempPointer to a pointer before
temp.next = prev.next;
prev.next = temp;
}
}
return dummyHead.next;
};
148. 排序链表
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 .
题解思路
这里使用归并排序
var sortList = function(head) {
//对链表进行：合
let mergeList = (left, right) => {
let res = new ListNode(0);
let pre = res;
while(left && right){
if(left.val <= right.val){
pre.next = left;
left = left.next;
} else {
pre.next = right;
right = right.next;
}
pre = pre.next;
}
pre.next = left || right;
return res.next;
}
let mergeSort = (node) => {
if(!node || !node.next) return node;
let mid = node, fast = node.next;
//通过while循环,Can find the list of the pointer in the middle of the
while(fast && fast.next){
mid = mid.next;
fast = fast.next.next;
}
//Here is the list：分
let rightList = mid.next;
mid.next = null;
let left = node, right = rightList;
return mergeList(mergeSort(left), mergeSort(right));
}
return mergeSort(head);
};
Using the merge sort of solving questions and：23. 合并K个升序链表
160. 相交链表
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表不存在相交节点,返回 null .
图示两个链表在节点 c1 开始相交：
题解思路
- curA指向链表A的头结点,curB指向链表B的头结点
- When drawing,让链表A和链表BAt the end of the alignment
- 求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到与curB相等的位置
- 此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点.否则循环退出返回空指针.
参考思路：160. 相交链表
var getListLen = function(head){
// 求链表的长度
let cur = head, len = 0;
while(cur){
len++;
cur = cur.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let curA = headA, curB = headB;
let lenA = getListLen(headA), lenB = getListLen(headB);
if(lenA < lenB){
// 让curA为最长链表的头,lenA为其长度
[curA, curB] = [curB, curA];
[lenA, lenB] = [lenB, lenA];
}
let i = lenA - lenB; // 求长度差
while(i-- > 0){
curA = curA.next; // 让curA和curB在同一起点上（末尾位置对齐）
}
while(curA && curA !== curB){
curA = curA.next;
curB = curB.next;
}
return curA;
};
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 .
题解思路
从头遍历,Meet the target node,直接删除
var removeElements = function(head, val) {
let dummyNode = new ListNode(-1); //设置一个虚拟头结点
dummyNode.next = head;
let prev = dummyNode; //prev记录当前节点的前一个节点
while(prev.next){
//从head开始遍历
if(prev.next.val === val){
//如果当前节点的值等于val
prev.next = prev.next.next;
}else{
prev = prev.next;
}
}
return dummyNode.next;
};
206. 反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表.
题解思路
var reverseList = function(head) {
if(!head || !head.next) return head;
let temp = null, pre = null, cur = head;
while(cur){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
};
234. 回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表.如果是,返回 true ;否则,返回 false .
题解思路
定义两个指针slow和fast初始分别指向head和head.next.
我们可以思考一下：slowEvery time go back,fastEvery time go back two,当fast或fast.next到链表末尾时,slowPointer moves to the center of the list（如果是奇数个节点,Coincides with the center;如果是偶数个节点,Is the center after a node）.
所以,当slowHaving walked to the center,我们只需要,将slow.nextIs the center list after a period of flip.
再将原来的headAnd in turnslow.next进行一一比对即可.
- 将链表一分为二,And then in turn part list
- Because if the chain length of the table is odd,The half part of the chain length of the table after less than a first half.
- So after traversal part list：如果元素相同,返回true.
- Second part for flip list：Can be individually encapsulated a function
- They turn over the list：Power button topic is similar to that of：206. 反转链表
var isPalindrome = function(head) {
let slow = head, fast = head.next;
//Through the slow pointer step,快指针走两步,Eventually the halfway point of the list can be found
while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;
}
let back = reverseList(slow.next);
while(back){
if(head.val !== back.val){
return false;
}
head = head.next;
back = back.next;
}
return true;
};
//Encapsulates a flip list function
function reverseList(head){
if(!head || !head.next) return head;
let temp = null, pre = null, cur = head;
while(cur){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
237. 删除链表中的节点
请编写一个函数,用于 删除单链表中某个特定节点 .在设计函数时需要注意,你无法访问链表的头节点 head ,只能直接访问 要被删除的节点 .
题目数据保证需要删除的节点 不是末尾节点 .
题解思路
根据链表的特点,删掉node,就是将node变成下一个节点.
Through the value,nextCover the deleted node to be deleted the next node.
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
328. 奇偶链表
给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表.
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推.
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致.
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题.
题解思路
Odd points to even under a,Even next to an odd number of,Finally the last item in the odd number of points to an even number first
var oddEvenList = function(head) {
if(head === null || head.next === null) return head;
let odd = head, even = head.next, evenStart = even;
while(even && even.next){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenStart;
return head;
};
445. 两数相加 II
给你两个 非空 链表来代表两个非负整数.数字最高位位于链表开始位置.它们的每个节点只存储一位数字.将这两数相加会返回一个新的链表.
你可以假设除了数字 0 之外,这两个数字都不会以零开头.
题解思路
- With two stack storage addend
- Then use a stack storage and
- 设置进位变量curry
- From the end of the two arrays of low addend,Find out and get more and the front of the inserted into the array(unshift)
- Finally, whether the final carry,如果有,Even in front of the array to add1
- And then will turn linked list and an array of
var addTwoNumbers = function(l1, l2) {
let stack1 = [], stack2 = [];
while(l1 !== null){
stack1.push(l1.val);
l1 = l1.next;
}
while(l2 !== null){
stack2.push(l2.val);
l2 = l2.next;
}
let sum = [];
let curry = 0;
let len1 = stack1.length - 1, len2 = stack2.length - 1;
while(len1 >= 0 || len2 >= 0){
let tmp1 = stack1[len1--] || 0, tmp2 = stack2[len2--] || 0;
sum.unshift((tmp1 + tmp2 + curry) % 10);
tmp1 + tmp2 + curry > 9 ? curry = 1 : curry = 0;
}
if(curry === 1) sum.unshift(1);
let dummy = cur = new ListNode(-1);
let i = 0;
while(i < sum.length){
cur.next = new ListNode(sum[i++], null);
cur = cur.next;
}
return dummy.next;
};
876. 链表的中间结点
给定一个头结点为 head 的非空单链表,返回链表的中间结点.
如果有两个中间结点,则返回第二个中间结点.
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 . (测评系统对该结点序列化表述是 [3,4,5]).
注意,我们返回了一个 ListNode 类型的对象 ans,这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点.
题解思路
使用两个指针变量,刚开始都位于链表的第 1 个结点,一个永远一次只走 1 步,一个永远一次只走 2 步,一个在前,一个在后,同时走.这样当快指针走完的时候,慢指针就来到了链表的中间位置.
当链表长度为奇数时：
当链表长度为偶数时：
var middleNode = function(head) {
slow = fast = head;
while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
边栏推荐
- Dynamic Agent Learning
- 1036 跟奥巴马一起编程 (15 分)
- tf中矩阵乘法
- NTT的Another Me技术助力创造歌舞伎演员中村狮童的数字孪生体，将在 “Cho Kabuki 2022 Powered by NTT”舞台剧中首次亮相
- 分布式锁-Redission - 缓存一致性解决
- 【LeetCode每日一题】——844.比较含退格的字符串
- Tidb二进制集群搭建
- Edge provides label grouping functionality
- TF generates (feature, label) set through feature and label, tf.data.Dataset.from_tensor_slices
- How Unity programmers can improve their abilities
猜你喜欢
随机推荐
1091 N-Defensive Number (15 points)
1071 Small Gamble (15 points)
Discourse's Close Topic and Reopen Topic
3.2 - classification - Logistic regression
项目2-年收入判断
STM32CUBEIDE（11）----输出PWM及修改PWM频率与占空比
2022-08-09 Group 4 Self-cultivation class study notes (every day)
About # SQL problem: how to set the following data by commas into multiple lines, in the form of column display
1081 检查密码 (15 分)
1096 big beautiful numbers (15 points)
年薪40W测试工程师成长之路，你在哪个阶段？
tf中矩阵乘法
4.1 - Support Vector Machines
1106 2019 Sequence (15 points)
Tf中的平方,多次方,开方计算
linux 安装mysql服务报错
DDR4内存条电路设计
分布式锁-Redission - 缓存一致性解决
oracle19c does not support real-time synchronization parameters, do you guys have any good solutions?
The most complete documentation on Excel's implementation of grouped summation