反轉(zhuǎn)鏈表
給你單鏈表的頭節(jié)點(diǎn) 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é)點(diǎn)為空，當(dāng)前節(jié)點(diǎn)為head
let pre = null;
let cur = head;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}移除鏈表
給你一個鏈表的頭節(jié)點(diǎn) head? 和一個整數(shù) val? ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點(diǎn)，并返回 「新的頭節(jié)點(diǎn)」 。
「示例 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é)點(diǎn)，簡化刪除頭節(jié)點(diǎn)
const dummy = new ListNode(null, head);
let pre = dummy;
let cur = dummy.next;
while (cur) {
// 如果找到該節(jié)點(diǎn)，改變節(jié)點(diǎn)關(guān)系，并將當(dāng)前節(jié)點(diǎn)改變?yōu)閚ext節(jié)點(diǎn)
if (cur.val === val) {
const next = cur.next;
pre.next = next;
cur = next;
} else {
// 如果不是該值節(jié)點(diǎn)，pre和cur節(jié)點(diǎn)都要改變
pre = cur;
cur = cur.next;
}
}
return dummy.next;
}交換鏈表
給你一個鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
「示例 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;
};
// 進(jìn)行反轉(zhuǎn)，返回反轉(zhuǎn)后的開始節(jié)點(diǎn)
const newHead = reverse(start, end);
// 通過遞歸，與后續(xù)節(jié)點(diǎn)連接
start.next = swapPairs(end);
return newHead;
}鏈表相交
給你兩個單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)。如果兩個鏈表沒有交點(diǎn)，返回 null 。
圖示兩個鏈表在節(jié)點(diǎn) c1 開始相交：
題目數(shù)據(jù) 保證 整個鏈?zhǔn)浇Y(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é)點(diǎn)的值為 8 （注意，如果兩個鏈表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節(jié)點(diǎn)前有 2 個節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)。
題解
// 雙指針解決
function getIntersectionNode(headA, headB) {
// p1指向headA的表頭結(jié)點(diǎn)；p2指向headB的表頭結(jié)點(diǎn)
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é)點(diǎn)
給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例 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é)點(diǎn)，方便刪除第一個節(jié)點(diǎn)的情況
const dummy = new ListNode(null, head);
let p1 = dummy;
let p2 = dummy;
// 因?yàn)橐獎h除倒數(shù)第n個節(jié)點(diǎn)，則p1則必須先走n + 1步，否則找到的則是倒數(shù)第n個，不能進(jìn)行刪除
for (let i = 0; i < n + 1; i++) {
p1 = p1.next;
}
// p1和p2一起往后走,知道p1走到終點(diǎn)，這樣p2就是要刪除的點(diǎn)
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
// 刪除倒數(shù)第n個節(jié)點(diǎn)
p2.next = p2.next.next;
return dummy.next;
}環(huán)形鏈表II
給定一個鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。如果鏈表無環(huán)，則返回 null。
如果鏈表中有某個節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實(shí)際情況。
不允許修改 鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1 輸出：返回索引為 1 的鏈表節(jié)點(diǎn) 解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點(diǎn)。
// 快慢指針
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;
}
// 將慢指針賦值給頭部，然后快慢指針都一起移動，相交點(diǎn)就是環(huán)形鏈表的入口節(jié)點(diǎn)
slow = head;
while (slow !== fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
