偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

十五周算法訓(xùn)練營——鏈表專題

開發(fā) 前端
本篇主要講鏈表專題,包含:反轉(zhuǎn)鏈表、移除鏈表、交換鏈表、鏈表相交、刪除鏈表中的倒數(shù)第N個節(jié)點、環(huán)形鏈表II。

反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點 head ,請你反轉(zhuǎn)鏈表,并返回反轉(zhuǎn)后的鏈表。

示例 1:

圖片

輸入:head = [1,2,3,4,5] 輸出:[5,4,3,2,1]。

function reverseList(head) {
if (head === null || head.next === null) {
return head;
}

// 設(shè)置初始的前一個節(jié)點為空,當(dāng)前節(jié)點為head
let pre = null;
let cur = head;

while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}

return pre;
}

移除鏈表

給你一個鏈表的頭節(jié)點 head? 和一個整數(shù) val? ,請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點,并返回 「新的頭節(jié)點」 。

「示例 1:」

圖片

輸入:head = [1,2,6,3,4,5,6], val = 6
輸出:[1,2,3,4,5]
function ListNode(val, next) {
this.val = val;
this.next = next || null;
}
function removeElement(head, val) {
// 借用一個空節(jié)點,簡化刪除頭節(jié)點
const dummy = new ListNode(null, head);

let pre = dummy;
let cur = dummy.next;

while (cur) {
// 如果找到該節(jié)點,改變節(jié)點關(guān)系,并將當(dāng)前節(jié)點改變?yōu)閚ext節(jié)點
if (cur.val === val) {
const next = cur.next;
pre.next = next;
cur = next;
} else {
// 如果不是該值節(jié)點,pre和cur節(jié)點都要改變
pre = cur;
cur = cur.next;
}
}

return dummy.next;
}

交換鏈表

給你一個鏈表,兩兩交換其中相鄰的節(jié)點,并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內(nèi)部的值的情況下完成本題(即,只能進行節(jié)點交換)。

「示例 1:」

圖片

輸入:head = [1,2,3,4]
輸出:[2,1,4,3]
function swapPairs(head) {
if (head === null || head.next === null) {
return head;
}

let k = 2;
let start = head;
let end = head;

// 找到[start, end),其是一組待反轉(zhuǎn)區(qū)間
for (let i = 0; i < k; i++) {
if (end === null) {
return head;
}

end = end.next;
}

// 反轉(zhuǎn)該部分
const reverse = (start, end) => {
if (start === null || start.next === null) {
return start;
}

let pre = null;
let cur = start;

while (cur !== end) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}

return pre;
};

// 進行反轉(zhuǎn),返回反轉(zhuǎn)后的開始節(jié)點
const newHead = reverse(start, end);

// 通過遞歸,與后續(xù)節(jié)點連接
start.next = swapPairs(end);

return newHead;
}

鏈表相交

給你兩個單鏈表的頭節(jié)點 headA 和 headB ,請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點,返回 null 。

圖示兩個鏈表在節(jié)點 c1 開始相交:

圖片

題目數(shù)據(jù) 保證 整個鏈式結(jié)構(gòu)中不存在環(huán)。

注意,函數(shù)返回結(jié)果后,鏈表必須 保持其原始結(jié)構(gòu) 。

示例 1:

圖片

輸入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 輸出:Intersected at '8' 解釋:相交節(jié)點的值為 8 (注意,如果兩個鏈表相交則不能為 0)。從各自的表頭開始算起,鏈表 A 為 [4,1,8,4,5],鏈表 B 為 [5,0,1,8,4,5]。在 A 中,相交節(jié)點前有 2 個節(jié)點;在 B 中,相交節(jié)點前有 3 個節(jié)點。

題解

// 雙指針解決
function getIntersectionNode(headA, headB) {
// p1指向headA的表頭結(jié)點;p2指向headB的表頭結(jié)點
let p1 = headA;
let p2 = headB;

while (p1 !== p2) {
// p1走一步,如果走到A鏈表末尾,轉(zhuǎn)到B鏈表
if (p1.next !== null) {
p1 = p1.next;
} else {
p1 = headB;
}

// p2走一步,如果走到B鏈表末尾,轉(zhuǎn)到A鏈表
if (p2.next !== null) {
p2 = p2.next;
} else {
p2 = headA;
}
}

return p1;
}

刪除鏈表中的倒數(shù)第N個節(jié)點

給你一個鏈表,刪除鏈表的倒數(shù)第 n 個結(jié)點,并且返回鏈表的頭結(jié)點。

示例 1:

圖片

輸入:head = [1,2,3,4,5], n = 2 輸出:[1,2,3,5]。

function ListNode(val, next) {
this.val = val;
this.next = next === undefined ? null : next;
}

function removeNthFromEnd(head, n) {
// 創(chuàng)建一個空節(jié)點,方便刪除第一個節(jié)點的情況
const dummy = new ListNode(null, head);
let p1 = dummy;
let p2 = dummy;

// 因為要刪除倒數(shù)第n個節(jié)點,則p1則必須先走n + 1步,否則找到的則是倒數(shù)第n個,不能進行刪除
for (let i = 0; i < n + 1; i++) {
p1 = p1.next;
}

// p1和p2一起往后走,知道p1走到終點,這樣p2就是要刪除的點
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}

// 刪除倒數(shù)第n個節(jié)點
p2.next = p2.next.next;

return dummy.next;
}

環(huán)形鏈表II

給定一個鏈表的頭節(jié)點  head ,返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán),則返回 null。

如果鏈表中有某個節(jié)點,可以通過連續(xù)跟蹤 next 指針再次到達,則鏈表中存在環(huán)。為了表示給定鏈表中的環(huán),評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。如果 pos 是 -1,則在該鏈表中沒有環(huán)。注意:pos 不作為參數(shù)進行傳遞,僅僅是為了標(biāo)識鏈表的實際情況。

不允許修改 鏈表。

示例 1:

圖片

輸入:head = [3,2,0,-4], pos = 1 輸出:返回索引為 1 的鏈表節(jié)點 解釋:鏈表中有一個環(huán),其尾部連接到第二個節(jié)點。

// 快慢指針
function detectCycle(head) {
if (head === null) {
return head;
}

let slow = head;
let fast = head;

while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;

// 快慢指針相遇說明有環(huán)
if (slow === fast) {
break;
}
}

// fast遇到空則表示不存在環(huán)
if (fast === null || fast.next === null) {
return null;
}

// 將慢指針賦值給頭部,然后快慢指針都一起移動,相交點就是環(huán)形鏈表的入口節(jié)點
slow = head;
while (slow !== fast) {
fast = fast.next;
slow = slow.next;
}

return slow;
}
責(zé)任編輯:姜華 來源: 前端點線面
相關(guān)推薦

2023-06-05 07:30:51

2023-05-22 07:31:32

Nums快慢指針

2023-05-29 07:31:35

單調(diào)棧數(shù)組循環(huán)

2023-05-15 07:32:01

算法訓(xùn)練滑動窗口

2023-07-10 08:01:13

島嶼問題算法

2023-04-03 07:33:05

數(shù)組排序快速排序法

2023-07-03 08:01:54

2023-06-26 07:31:44

屬性物品背包

2023-06-13 06:51:15

斐波那契數(shù)算法

2023-06-19 07:31:34

普通動態(tài)規(guī)劃字符串

2021-09-23 10:53:43

數(shù)據(jù)中心

2016-08-05 20:21:51

CTO導(dǎo)師技術(shù)

2016-08-05 18:53:25

CTO導(dǎo)師技術(shù)

2021-07-08 20:22:05

AI

2013-04-22 12:58:14

TechExcel敏捷研發(fā)

2009-04-29 18:12:41

GAUPS培訓(xùn)

2013-07-13 22:38:14

微軟社區(qū)微軟MVPMWW

2016-10-17 13:50:31

2015-01-04 14:54:28

IT訓(xùn)練營

2016-08-04 13:41:27

CTO訓(xùn)練營,技術(shù)管理
點贊
收藏

51CTO技術(shù)棧公眾號