一余指、反轉(zhuǎn)問題
2021.02.11
No.25 K個(gè)一組翻轉(zhuǎn)鏈表
給你一個(gè)鏈表捕犬，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表。
k 是一個(gè)正整數(shù)碉碉，它的值小于或等于鏈表的長(zhǎng)度柴钻。
如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序垢粮。
示例：
給你這個(gè)鏈表：1->2->3->4->5
當(dāng) k = 2 時(shí)贴届，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5
說明：
你的算法只能使用常數(shù)的額外空間蜡吧。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值毫蚓，而是需要實(shí)際進(jìn)行節(jié)點(diǎn)交換。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有斩跌。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)绍些，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處捞慌。
方案一：
/*
* @lc app=leetcode.cn id=25 lang=javascript
*
* [25] K 個(gè)一組翻轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 對(duì)k個(gè)節(jié)點(diǎn)進(jìn)行數(shù)組切割即可
const kReverse = (a,k) => {
const r = [];
let cnt = 0;
while(a.length >= k + cnt)
{
let tmp = a.slice(cnt, cnt+k);
tmp.reverse();
tmp.map( (x)=> r.push(x));
cnt += k;
}
a.slice(cnt).map( (x)=> r.push(x));
return r;
}
return arr2List(kReverse(list2Arr(head), k));
};
方案二：
/*
* @lc app=leetcode.cn id=25 lang=javascript
*
* [25] K 個(gè)一組翻轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
let cur = head;
let count = 0;
// 求k個(gè)待反轉(zhuǎn)元素的首節(jié)點(diǎn)和尾節(jié)點(diǎn)
while(cur != null && count != k){
cur = cur.next;
count++;
}
// 足夠k個(gè)節(jié)點(diǎn)耀鸦，去反轉(zhuǎn)
if(count == k){
// 遞歸鏈接后續(xù)k個(gè)反轉(zhuǎn)的鏈表頭節(jié)點(diǎn)
cur = reverseKGroup(cur,k);
while(count != 0){
count--;
// 反轉(zhuǎn)鏈表
let tmp = head.next;
head.next = cur;
cur = head;
head = tmp;
}
head = cur;
}
return head;
};
方案三：
/*
* @lc app=leetcode.cn id=25 lang=javascript
*
* [25] K 個(gè)一組翻轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if(!head) return null;
// 反轉(zhuǎn)鏈表
let reverse = (a,b) => {
let pre;
let cur = a;
let next = b;
while(cur != b){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
// 反轉(zhuǎn)區(qū)間a-b的k個(gè)待反轉(zhuǎn)的元素
let a = head;
let b = head;
for(let i = 0;i < k;i++){
// 不足k個(gè)，不需要反轉(zhuǎn)
if(!b) return head;
b = b.next;
}
// 反轉(zhuǎn)前k個(gè)元素
let newHead = reverse(a,b);
// 遞歸鏈接后續(xù)反轉(zhuǎn)鏈表
a.next = reverseKGroup(b,k);
return newHead;
};
方案四：
/*
* @lc app=leetcode.cn id=25 lang=javascript
*
* [25] K 個(gè)一組翻轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
let stack = [];
let preHead = new ListNode(0);
let pre = preHead;
// 循環(huán)鏈接后續(xù)反轉(zhuǎn)鏈表
while(true){
let count = 0;
let tmp = head;
while(tmp && count < k){
stack.push(tmp);
tmp = tmp.next;
count++;
}
// 不夠k個(gè)啸澡，直接鏈接剩下鏈表返回
if(count != k){
pre.next = head;
break;
}
// 出棧即是反轉(zhuǎn)
while(stack.length > 0){
pre.next = stack.pop();
pre = pre.next;
}
pre.next = tmp;
head = tmp;
}
return preHead.next;
};
方案五：
/*
* @lc app=leetcode.cn id=25 lang=javascript
*
* [25] K 個(gè)一組翻轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
const myReverse = (head, tail) => {
let prev = tail.next;
let p = head;
while (prev !== tail) {
const nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return [tail, head];
}
const hair = new ListNode(0);
hair.next = head;
let pre = hair;
while (head) {
let tail = pre;
// 查看剩余部分長(zhǎng)度是否大于等于 k
for (let i = 0; i < k; ++i) {
tail = tail.next;
if (!tail) {
return hair.next;
}
}
const nex = tail.next;
[head, tail] = myReverse(head, tail);
// 把子鏈表重新接回原鏈表
pre.next = head;
tail.next = nex;
pre = tail;
head = tail.next;
}
return hair.next;
};
有五種解法：1袖订、利用數(shù)組求解，比較笨重嗅虏，需要切換成數(shù)組再切回來(lái)洛姑；2、遞歸相關(guān)方案皮服，利用棧楞艾、迭代等進(jìn)行解析；3龄广、利用虛置前節(jié)點(diǎn)硫眯，將復(fù)雜度降到常數(shù)級(jí)別，很巧妙
2021.02.12
No.61 旋轉(zhuǎn)鏈表
給定一個(gè)鏈表择同，旋轉(zhuǎn)鏈表两入，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)敲才。
示例 1:
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL
示例 2:
輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL
向右旋轉(zhuǎn) 4 步: 2->0->1->NULL
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotate-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有裹纳。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處紧武。
方案一：
/*
* @lc app=leetcode.cn id=61 lang=javascript
*
* [61] 旋轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 數(shù)組位置變化
const arrRotate = (a, k) => {
const len = a.length;
const hashTable = {};
for(let i=0; i< a.length; i++) {
hashTable[(i+k) % len] = a[i]
};
return Object.values(hashTable)
};
return arr2List(arrRotate(list2Arr(head), k));
};
方案二：
/*
* @lc app=leetcode.cn id=61 lang=javascript
*
* [61] 旋轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function (head, k) {
if (!head || k === 0) return head; // 特判
let p = head, len = 1;
while (p.next) {
p = p.next;
len++;
}
p.next = head; // 首尾相接
k = len - k % len; // 處理要移動(dòng)的距離
while (k--) p = p.next;
head = p.next; // head 指向第 len - k + 1 個(gè)節(jié)點(diǎn)剃氧，即答案
p.next = null; // 切斷 len - k 與 len - k + 1 的關(guān)系
return head;
}
方案三：
/*
* @lc app=leetcode.cn id=61 lang=javascript
*
* [61] 旋轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if(head===null||head.next===null)return head;
let len = 0;//鏈表長(zhǎng)度
let p = head;
let first = head;//第一個(gè)結(jié)點(diǎn)
let stack = [];//輔助棧
while(p){
stack.push(p);
p = p.next;
len++;
}
p = stack.pop();
for(let i = 1;i<=k%len;i++){
p.next = first;
stack.unshift(p);
first = p;
p = stack.pop();
p.next = null;
}
return first;
};
方案四：
/*
* @lc app=leetcode.cn id=61 lang=javascript
*
* [61] 旋轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
var order = new ListNode(0,head); // head鏈表的copy
var fast = new ListNode(0,head); // 快指針
var slow = new ListNode(0,head); // 慢指針
var count = 0; // 鏈表長(zhǎng)度
while(order && order.next){ // 循環(huán)求鏈表長(zhǎng)度
order = order.next;
count ++;
}
var n = k % count; // 因?yàn)?k > 鏈表長(zhǎng)度 時(shí)，出現(xiàn)重復(fù)操作阻星。對(duì) k 求余,去除重復(fù)
for (var i = 0; i < n; i++){ // 快指針先走 n 步
fast = fast.next;
}
while(fast && fast.next){ // 鏈表的快指針朋鞍、慢指針操作
fast = fast.next;
slow = slow.next;
}
// 兩步操作
// 第一、將倒數(shù)第 k%count 元素 與 倒數(shù)第 (k%count-1) 元素 斷開
var resultPre = slow.next; // 序號(hào)2 返回結(jié)果集的 起始位置
var result = resultPre; // 序號(hào)3 最后return的結(jié)果集
slow.next = null; // 將鏈表斷開
// 第二、再講鏈表的尾部與頭部鏈接
while(resultPre && resultPre.next) {
resultPre = resultPre.next
}
if (resultPre){
resultPre.next = head; // 情況1：旋轉(zhuǎn)鏈表后有改變番舆，將鏈表拼接起來(lái)
}
else {
result = head; // 情況2: 旋轉(zhuǎn)鏈表后沒有改變酝碳，返回原始鏈表
}
return result;
};
方案五：
/*
* @lc app=leetcode.cn id=61 lang=javascript
*
* [61] 旋轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
const rotateRight = (head, k) => {
if (!head || !head.next) return head
let curr = head, n = 0
// 遍歷鏈表計(jì)算其長(zhǎng)度
while (++n && curr.next) curr = curr.next
k = k % n // 去重
// 鏈表右移
while (k--) {
curr = head
while (curr.next.next) curr = curr.next
// 這里curr是鏈表的打斷位置，即倒數(shù)第二項(xiàng)
curr.next.next = head // 鏈表最后一項(xiàng)指向頭部形成環(huán)
head = curr.next // 定位新的頭節(jié)點(diǎn)
curr.next = null // 打斷鏈表環(huán)
}
return head
}
本題有五種思路：1恨狈、hash表存儲(chǔ)疏哗，利用數(shù)組的位置排序進(jìn)行hash斂散生成新的鏈表；2禾怠、鏈表成環(huán)返奉，對(duì)應(yīng)位置剪開；3吗氏、堆棧輔助處理循環(huán)剪斷位置芽偏；4、快慢指針弦讽，根據(jù)雙指針的位置間距進(jìn)行處理污尉，對(duì)新剪開位置使用另外兩個(gè)指針記錄處理；5往产、常規(guī)窮舉被碗，一步一步進(jìn)行
2021.02.13
No.92 翻轉(zhuǎn)鏈表-ii
反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)仿村。
說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度锐朴。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)蔼囊，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處焚志。
方案一：
/*
* @lc app=leetcode.cn id=92 lang=javascript
*
* [92] 反轉(zhuǎn)鏈表 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 數(shù)組 m => n 翻轉(zhuǎn)
const reversePosition = (a, m, n) => {
return [...a.slice(0,m-1), ...a.slice(m-1,n).reverse(), ...a.slice(n)]
};
return arr2List(reversePosition(list2Arr(head),m,n));
};
方案二：
/*
* @lc app=leetcode.cn id=92 lang=javascript
*
* [92] 反轉(zhuǎn)鏈表 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
// step1 => 雙指針p1,p2保持固定間距
const dummyHead = new ListNode(0, head);
let p1 = p2 = head;
let step2 = n - m;
while (step2-- > 0) {
p2 = p2.next;
}
let step1 = m - 1;
let tmpHead = p1;
while (step1-- > 0) {
tmpHead = p1;
p1 = p1.next;
p2 = p2.next;
}
// step2 => 極其重要的測(cè)試case：p1指針壓根沒動(dòng)【dummyHead就起作用了】
if (p1 == head) {
tmpHead = dummyHead;
}
// step3 => 尾插法
let tmp = p1;
while (tmp != p2) {
tmp = p1.next;
p1.next = tmp.next;
tmp.next = tmpHead.next;
tmpHead.next = tmp;
}
return dummyHead.next;
};
兩種解法：1、轉(zhuǎn)成數(shù)組畏鼓，利用數(shù)組的slice及reverse拼接酱酬；2、雙指針+尾插法滴肿，利用頭尾指針的交換
2021.02.14
No.206 反轉(zhuǎn)鏈表
反轉(zhuǎn)一個(gè)單鏈表岳悟。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
方案一：
/*
* @lc app=leetcode.cn id=206 lang=javascript
*
* [206] 反轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 數(shù)組 m => n 翻轉(zhuǎn)
const reverseList = (a) => {
return a.reverse()
};
return arr2List(reverseList(list2Arr(head)));
};
方案二：
/*
* @lc app=leetcode.cn id=206 lang=javascript
*
* [206] 反轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
方案三：
/*
* @lc app=leetcode.cn id=206 lang=javascript
*
* [206] 反轉(zhuǎn)鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head == null || head.next == null) {
return head;
}
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};
三種方法：1、轉(zhuǎn)成數(shù)組泼差，利用數(shù)組的reverse贵少；2、迭代堆缘；3.遞歸
總結(jié)：
- 反轉(zhuǎn)鏈表問題常見的利用鏈表的三指針進(jìn)行相關(guān)的反轉(zhuǎn)滔灶，常見的為頭指針、尾指針及替換指針的相關(guān)變形吼肥，可以利用棧等數(shù)據(jù)結(jié)構(gòu)進(jìn)行迭代或遞歸录平；
- 對(duì)于反轉(zhuǎn)問題有一個(gè)取巧的辦法就是將其轉(zhuǎn)成數(shù)組后利用數(shù)組的相關(guān)api進(jìn)行處理麻车，再將數(shù)組轉(zhuǎn)為鏈表
二、分隔合并
2021.02.18
No.21 合并兩個(gè)有序鏈表
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回斗这。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的动猬。
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
提示：
兩個(gè)鏈表的節(jié)點(diǎn)數(shù)目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)表箭，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處赁咙。
方案一：
/*
* @lc app=leetcode.cn id=21 lang=javascript
*
* [21] 合并兩個(gè)有序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
if(!l1) return l2;
if(!l2) return l1;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
};
方案二：
/*
* @lc app=leetcode.cn id=21 lang=javascript
*
* [21] 合并兩個(gè)有序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
let prev = new ListNode(-1),
head = prev;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
}
head.next = l1 === null ? l2 : l1;
return prev.next;
};
方案三：
/*
* @lc app=leetcode.cn id=21 lang=javascript
*
* [21] 合并兩個(gè)有序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 兩個(gè)數(shù)組合并排序
const mergeArr = (a1,a2) => {
return [...a1,...a2].sort((a,b) => a-b);
}
return arr2List(mergeArr(list2Arr(l1), list2Arr(l2)));
};
有三種方案：1、遞歸免钻，利用隱式棧進(jìn)行鏈表的合并彼水；2、迭代极舔，使用雙指針進(jìn)行迭代判斷凤覆；3、轉(zhuǎn)化成數(shù)組合并升序排列
2021.02.21
No.23 合并k個(gè)升序鏈表
給你一個(gè)鏈表數(shù)組拆魏，每個(gè)鏈表都已經(jīng)按升序排列盯桦。
請(qǐng)你將所有鏈表合并到一個(gè)升序鏈表中，返回合并后的鏈表稽揭。
示例 1：
輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數(shù)組如下：
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個(gè)有序鏈表中得到俺附。
1->1->2->3->4->4->5->6
示例 2：
輸入：lists = []
輸出：[]
示例 3：
輸入：lists = [[]]
輸出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的總和不超過 10^4
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)溪掀，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案一：
/*
* @lc app=leetcode.cn id=23 lang=javascript
*
* [23] 合并K個(gè)升序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 對(duì)k個(gè)節(jié)點(diǎn)進(jìn)行數(shù)組切割即可
const mergeArr = lists => {
const r = [];
lists.forEach(list => r.push(...list2Arr(list)))
return r.sort((a,b) => a-b);
}
return arr2List(mergeArr(lists));
};
方案二：
/*
* @lc app=leetcode.cn id=23 lang=javascript
*
* [23] 合并K個(gè)升序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 合并兩個(gè)鏈表
const mergeTwoLists = function(l1, l2) {
let prev = new ListNode(-1),
head = prev;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
}
head.next = l1 === null ? l2 : l1;
return prev.next;
};
// 分治
const merge = (lists, l, r) => {
if (l == r) return lists[l];
if (l > r) return null;
const mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
};
return merge(lists, 0, lists.length - 1);
};
方案三：
/*
* @lc app=leetcode.cn id=23 lang=javascript
*
* [23] 合并K個(gè)升序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
let queue = new PriorityQueue();
lists.forEach(list => {
if(list) queue.enqueue(list, list.val)
});
let res = new ListNode(-1);
let cur = res;
while(!queue.isEmpty()) {
cur.next = queue.dequeue();
cur = cur.next;
if(cur.next) queue.enqueue(cur.next, cur.next.val);
}
return res.next;
}
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) {
let node = new Node(val, priority);
this.values.push(node);
this.bubbleUp();
}
dequeue() {
let max = this.values[0];
let end = this.values.pop();
if(this.values.length) {
this.values[0] = end;
this.bubbleDown();
}
return max.val;
}
isEmpty() {
return !this.values.length;
}
bubbleUp(index = this.values.length - 1) {
if(index <= 0) return;
let parentIndex = Math.floor((index - 1) / 2);
if(this.values[index].priority <= this.values[parentIndex].priority) {
[this.values[index], this.values[parentIndex]] = [this.values[parentIndex], this.values[index]];
this.bubbleUp(parentIndex);
}
}
bubbleDown(index = 0, swapIndex = null) {
let leftIndex = index * 2 + 1,
rightIndex = index * 2 + 2,
length = this.values.length;
if(leftIndex < length) {
if(this.values[leftIndex].priority <= this.values[index].priority) {
swapIndex = leftIndex;
}
}
if(rightIndex < length) {
if((swapIndex === null && this.values[rightIndex].priority <= this.values[index].priority) || (swapIndex !== null && this.values[rightIndex].priority <= this.values[leftIndex].priority)) {
swapIndex = rightIndex;
}
}
if(swapIndex !== null) {
[this.values[index], this.values[swapIndex]] = [this.values[swapIndex], this.values[index]];
this.bubbleDown(swapIndex, null);
}
}
};
有三種解法：1步鉴、利用數(shù)組解決揪胃，最后將數(shù)組轉(zhuǎn)為鏈表；2氛琢、結(jié)合合并兩個(gè)鏈表方案喊递，利用分治算法優(yōu)化；3阳似、構(gòu)造優(yōu)先隊(duì)列進(jìn)行優(yōu)化骚勘，利用空間換時(shí)間
2021.02.22
No.86 分隔鏈表
給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x ，請(qǐng)你對(duì)鏈表進(jìn)行分隔撮奏，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前俏讹。
你應(yīng)當(dāng) 保留 兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置。
示例 1：
輸入：head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]
示例 2：
輸入：head = [2,1], x = 2
輸出：[1,2]
提示：
鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 200] 內(nèi)
-100 <= Node.val <= 100
-200 <= x <= 200
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有畜吊。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)泽疆，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案一：
/*
* @lc app=leetcode.cn id=86 lang=javascript
*
* [86] 分隔鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
let a = new ListNode(0),
b = new ListNode(0);
const ahead = a,
bhead = b;
while(head) {
if(head.val < x) {
a.next = head;
a = a.next;
} else {
b.next = head;
b = b.next;
}
head = head.next;
}
a.next = bhead.next;
b.next = null;
return ahead.next;
};
方案二：
/*
* @lc app=leetcode.cn id=86 lang=javascript
*
* [86] 分隔鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 數(shù)組排序
const arrSort = (arr, x) => {
return [...arr.filter(a => a < x), ...arr.filter(a => a >= x)];
};
return arr2List(arrSort(list2Arr(head), x))
};
有兩種解法：1玲献、分成大小鏈表后合并殉疼；2梯浪、利用數(shù)組api排序
2021.03.02
No.725 分隔鏈表
給定一個(gè)頭結(jié)點(diǎn)為 root 的鏈表, 編寫一個(gè)函數(shù)以將鏈表分隔為 k 個(gè)連續(xù)的部分。
每部分的長(zhǎng)度應(yīng)該盡可能的相等: 任意兩部分的長(zhǎng)度差距不能超過 1瓢娜，也就是說可能有些部分為 null挂洛。
這k個(gè)部分應(yīng)該按照在鏈表中出現(xiàn)的順序進(jìn)行輸出，并且排在前面的部分的長(zhǎng)度應(yīng)該大于或等于后面的長(zhǎng)度眠砾。
返回一個(gè)符合上述規(guī)則的鏈表的列表抹锄。
舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]
示例 1：
輸入:
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應(yīng)該是鏈表，而不是數(shù)組荠藤。
例如, 輸入的結(jié)點(diǎn) root 的 val= 1, root.next.val = 2, oot.next.next.val = 3, 且 root.next.next.next = null伙单。
第一個(gè)輸出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一個(gè)元素 output[4] 為 null, 它代表了最后一個(gè)部分為空鏈表哈肖。
示例 2：
輸入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解釋:
輸入被分成了幾個(gè)連續(xù)的部分吻育，并且每部分的長(zhǎng)度相差不超過1.前面部分的長(zhǎng)度大于等于后面部分的長(zhǎng)度。
提示:
root 的長(zhǎng)度范圍： [0, 1000].
輸入的每個(gè)節(jié)點(diǎn)的大小范圍：[0, 999].
k 的取值范圍： [1, 50].
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有淤井。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)布疼，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案：
/*
* @lc app=leetcode.cn id=725 lang=javascript
*
* [725] 分隔鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} root
* @param {number} k
* @return {ListNode[]}
*/
var splitListToParts = function (root, k) {
// 1. 獲取鏈表的長(zhǎng)度
const getRootLength = root => {
let n = 0;
while (root) {
n++;
root = root.next;
};
return n;
};
// 2. 分析鏈表的分割方式
// b項(xiàng)是 a+1币狠；k-b項(xiàng)是 a
const len = getRootLength(root),
a = ~~(len / k),
b = len % k;
// 3. 分割鏈表
const r = []; // 返回的鏈表數(shù)組
// 循環(huán)鏈表
for(let m = 1;m<=k;m++) {
if(!root) {
r.push(null);
continue;
}
let p1 = root,
p2 = root,
num = a;
if(m<=b) {
while(num-->0) p2 = p2.next;
} else {
num -=1;
while(num-->0) p2 = p2.next;
};
// 處理p2為null
if(!p2) {
r.push(p1);
root = null;
continue;
}
root = p2.next;
p2.next = null;
r.push(p1);
}
return r;
};
關(guān)鍵在于對(duì)k的分離游两，判斷不同的分割長(zhǎng)度，對(duì)邊界條件處理需要注意
總結(jié)：
- 鏈表的合并與分割主要新鏈表的構(gòu)造漩绵，需要根據(jù)要求進(jìn)行拆分與組合贱案，常見的構(gòu)造鏈表有雙指針法及堆棧法
- 特殊的，由于js沒有自己的鏈表結(jié)構(gòu)止吐，因而可以將鏈表轉(zhuǎn)為數(shù)組宝踪，利用相關(guān)api去處理
三、刪除節(jié)點(diǎn)
2021.03.04
No.203 移除鏈表元素
刪除鏈表中等于給定值 _val _的所有節(jié)點(diǎn)碍扔。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
方案：
/*
* @lc app=leetcode.cn id=203 lang=javascript
*
* [203] 移除鏈表元素
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
if(!head) return null;
let p = phead = new ListNode(null);
p.next = head;
while(p.next) {
if(p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return phead.next;
};
鏈表的構(gòu)造瘩燥，使用啞節(jié)點(diǎn)構(gòu)造頭指針進(jìn)行雙指針遍歷
2021.03.06
No.19 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)不同，并且返回鏈表的頭結(jié)點(diǎn)厉膀。
進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？
示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]
提示：
鏈表中結(jié)點(diǎn)的數(shù)目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有二拐。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)服鹅，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案一：
/*
* @lc app=leetcode.cn id=19 lang=javascript
*
* [19] 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let p = head, q = head, m = phead = new ListNode(head);
m.next = head;
// 將q指針變?yōu)?q = head.next···next 有n個(gè)next
for( let _n = n; _n > 0; _n-- ) {
q = head.next;
head = head.next;
};
// 當(dāng)q為null時(shí) 停止遍歷
while(q) {
p = p.next;
q = q.next;
m = m.next;
};
// 刪除此時(shí)q的節(jié)點(diǎn)
p = p.next;
m.next = p;
return phead.next;
};
方案二：
/*
* @lc app=leetcode.cn id=19 lang=javascript
*
* [19] 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let lastN = 0;
const recursion = (head) => {
if (!head) {
return null;
}
const next = recursion(head.next);
lastN++;
if (lastN === n) {
head = next;
}
if (lastN === n + 1) {
head.next = next;
}
return head;
};
return recursion(head);
};
方案三：
/*
* @lc app=leetcode.cn id=19 lang=javascript
*
* [19] 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
const nowHead = [head];
let tempHead = head;
while (tempHead.next) {
nowHead.push(tempHead.next);
tempHead = tempHead.next;
}
let lastN = 0;
let isHead = true;
while (nowHead.length) {
lastN++;
const now = nowHead.pop();
if (lastN - 1 === n) {
isHead = false;
now.next = now.next.next;
}
}
if (isHead) {
head = head.next;
}
return head;
};
有三種方案：1卓鹿、快慢指針菱魔，設(shè)置快慢指針間距為n，進(jìn)行遍歷吟孙；2澜倦、遞歸聚蝶；3、迭代
2021.03.09
No.82 刪除排序鏈表中的重復(fù)元素 ii
給定一個(gè)排序鏈表藻治，刪除所有含有重復(fù)數(shù)字的節(jié)點(diǎn)碘勉，只保留原始鏈表中 沒有重復(fù)出現(xiàn) 的數(shù)字。
示例 1:
輸入: 1->2->3->3->4->4->5
輸出: 1->2->5
示例 2:
輸入: 1->1->1->2->3
輸出: 2->3
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有桩卵。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)验靡，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案：
/*
* @lc app=leetcode.cn id=82 lang=javascript
*
* [82] 刪除排序鏈表中的重復(fù)元素 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
if (!head) return null;
let h = p = new ListNode(head),
q = head;
h.next = head;
p.next = head
while (q && q.next) {
if ( q.val == q.next.val) {
while(q.next && q.val == q.next.val) q = q.next;
p.next = q.next;
} else {
p = p.next;
}
q = q.next;
}
return h.next;
};
雙指針處理雏节，需要注意邊界處理
2021.03.10
No.83 刪除排序鏈表中的重復(fù)元素
給定一個(gè)排序鏈表胜嗓，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次钩乍。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有辞州。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處寥粹。
方案一：
/*
* @lc app=leetcode.cn id=83 lang=javascript
*
* [83] 刪除排序鏈表中的重復(fù)元素
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
if(!head) return null;
let h = p = new ListNode(head),
q = head;
h.next = head;
p.next = head;
while(q && q.next) {
if(q.next.val == q.val) {
while(q.next && q.next.val == q.val) {
q = q.next;
}
p.next = q;
}
p = p.next;
q = q.next;
};
return h.next;
};
方案二：
/*
* @lc app=leetcode.cn id=83 lang=javascript
*
* [83] 刪除排序鏈表中的重復(fù)元素
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
if(!head || !head.next) return head;
head.next = deleteDuplicates(head.next);
if(head.next.val == head.val) {
head.next = head.next.next;
}
return head;
};
同82題变过，有兩種方案：1、快慢指針涝涤，也可以使用單指針遍歷媚狰；2、遞歸
2021.03.11
No.237 刪除鏈表中的節(jié)點(diǎn)
請(qǐng)編寫一個(gè)函數(shù)阔拳，使其可以刪除某個(gè)鏈表中給定的（非末尾）節(jié)點(diǎn)崭孤。傳入函數(shù)的唯一參數(shù)為 要被刪除的節(jié)點(diǎn) 。
現(xiàn)有一個(gè)鏈表 -- head = [4,5,1,9]衫生，它可以表示為:
示例 1：
輸入：head = [4,5,1,9], node = 5
輸出：[4,1,9]
解釋：給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)裳瘪，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.
示例 2：
輸入：head = [4,5,1,9], node = 1
輸出：[4,5,9]
解釋：給定你鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)罪针，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.
提示：
鏈表至少包含兩個(gè)節(jié)點(diǎn)黄伊。
鏈表中所有節(jié)點(diǎn)的值都是唯一的泪酱。
給定的節(jié)點(diǎn)為非末尾節(jié)點(diǎn)并且一定是鏈表中的一個(gè)有效節(jié)點(diǎn)。
不要從你的函數(shù)中返回任何結(jié)果还最。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有墓阀。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處拓轻。
方案：
/*
* @lc app=leetcode.cn id=237 lang=javascript
*
* [237] 刪除鏈表中的節(jié)點(diǎn)
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
if(!node) return null;
node.val = node.next.val;
node.next = node.next.next;
};
沒有頭結(jié)點(diǎn)刪除節(jié)點(diǎn)的方案斯撮，移花接木，需要替換當(dāng)前值扶叉，然后刪除下一個(gè)節(jié)點(diǎn)值
總結(jié)：
- 刪除節(jié)點(diǎn)最常見的方案是快慢指針的遍歷刪除勿锅，快指針探索帕膜，慢指針作為最后需要返回的鏈表路徑對(duì)節(jié)點(diǎn)進(jìn)行相應(yīng)的控制；
- 也可以使用遞歸溢十、迭代垮刹、棧等額外的空間來(lái)?yè)Q取相應(yīng)的時(shí)間效率
四、特殊鏈表
2021.03.15
No.141 環(huán)形鏈表
給定一個(gè)鏈表张弛，判斷鏈表中是否有環(huán)荒典。
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)吞鸭，則鏈表中存在環(huán)寺董。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）刻剥。 如果 pos 是 -1遮咖，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞透敌，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況盯滚。
如果鏈表中存在環(huán)，則返回 true 酗电。 否則魄藕，返回 false 。
進(jìn)階：
你能用 O(1)（即撵术，常量）內(nèi)存解決此問題嗎靡挥？
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)笙瑟，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)竣贪。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。
提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個(gè) 有效索引 杜漠。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有腰湾。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處处坪。
方案一：
/*
* @lc app=leetcode.cn id=141 lang=javascript
*
* [141] 環(huán)形鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
if(!head) return false;
let hash = new Map();
while(head) {
if(hash.has(head)) return true;
hash.set(head, true);
head = head.next;
}
return false;
};
方案二：
/*
* @lc app=leetcode.cn id=141 lang=javascript
*
* [141] 環(huán)形鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let fast = head;
let slow = head;
while (fast) {
if (fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
};
方案三：
/*
* @lc app=leetcode.cn id=141 lang=javascript
*
* [141] 環(huán)形鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
try {
JSON.stringify(head)
return false
} catch {
return true
}
};
有三種解法：1根资、構(gòu)造hash表；2同窘、快慢指針判斷玄帕；3、取巧想邦，利用JSON.stringify的不能循環(huán)引用
2021.04.26
No.160 相交鏈表
編寫一個(gè)程序裤纹，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。
如下面的兩個(gè)鏈表：
在節(jié)點(diǎn) c1 開始相交丧没。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節(jié)點(diǎn)的值為 8 （注意鹰椒，如果兩個(gè)鏈表相交則不能為 0）锡移。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]吹零，鏈表 B 為 [5,0,1,8,4,5]罩抗。在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)灿椅；在 B 中套蒂，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。
示例 2：
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋：相交節(jié)點(diǎn)的值為 2 （注意茫蛹，如果兩個(gè)鏈表相交則不能為 0）操刀。從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]婴洼，鏈表 B 為 [3,2,4]骨坑。在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)柬采；在 B 中欢唾，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。
示例 3：
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
輸入解釋：從各自的表頭開始算起粉捻，鏈表 A 為 [2,6,4]礁遣，鏈表 B 為 [1,5]。由于這兩個(gè)鏈表不相交肩刃，所以 intersectVal 必須為 0祟霍，而 skipA 和 skipB 可以是任意值。
解釋：這兩個(gè)鏈表不相交盈包，因此返回 null沸呐。
注意：
如果兩個(gè)鏈表沒有交點(diǎn)，返回 null.
在返回結(jié)果后呢燥，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)崭添。
可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)。
程序盡量滿足 O(n) 時(shí)間復(fù)雜度叛氨，且僅用 O(1) 內(nèi)存滥朱。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)力试，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案一：
/*
* @lc app=leetcode.cn id=160 lang=javascript
*
* [160] 相交鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
let pA = headA;
while (pA) {
let pB = headB;
while (pB) {
if (pA === pB) return pA;
pB = pB.next;
}
pA = pA.next;
}
};
方案二：
/*
* @lc app=leetcode.cn id=160 lang=javascript
*
* [160] 相交鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
const hashmap = new Map();
let pA = headA;
while (pA) {
hashmap.set(pA, 1);
pA = pA.next;
}
let pB = headB;
while (pB) {
if (hashmap.has(pB)) return pB;
pB = pB.next;
}
};
方案三：
/*
* @lc app=leetcode.cn id=160 lang=javascript
*
* [160] 相交鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
let pA = headA,
pB = headB;
while(pA != pB) {
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
return pA;
};
方案四：
/*
* @lc app=leetcode.cn id=160 lang=javascript
*
* [160] 相交鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
let aNum = 0
let bNum = 0
let short = headA
let long = headB
let tempA = headA
let tempB = headB
while (short) {
aNum += 1
short = short.next
}
while (long) {
bNum += 1
long = long.next
}
if (aNum > bNum) {
let dig = aNum - bNum
for (let i = 0; i < dig; i++) {
tempA = tempA.next
}
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next
}
}
}
if (aNum < bNum) {
let dig = bNum - aNum
for (let i = 0; i < dig; i++) {
tempB = tempB.next
}
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next
}
}
}
if (aNum = bNum) {
while (tempA) {
if(tempA == tempB) {
return tempA
} else {
tempA = tempA.next
tempB = tempB.next
}
}
}
};
有四種方案：1排嫌、暴解畸裳，讓A去找B；2淳地、先遍歷一遍生成hash表怖糊，然后判斷帅容；3、形成交叉的環(huán)形鏈表伍伤，交叉遍歷并徘；4、先遍歷算出最長(zhǎng)表扰魂，讓最長(zhǎng)表先走然后同步判斷
2021.04.27
No.142 環(huán)形鏈表 ii
給定一個(gè)鏈表麦乞，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)劝评，則返回 null姐直。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）蒋畜。 如果 pos 是 -1声畏，則在該鏈表中沒有環(huán)。注意姻成，pos 僅僅是用于標(biāo)識(shí)環(huán)的情況插龄，并不會(huì)作為參數(shù)傳遞到函數(shù)中。
說明：不允許修改給定的鏈表科展。
進(jìn)階：
你是否可以使用 O(1) 空間解決此題均牢？
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)辛润。
示例 2：
輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)膨处，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例 3：
輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)砂竖。
提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個(gè)有效索引
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有真椿。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處乎澄。
方案一：
/*
* @lc app=leetcode.cn id=142 lang=javascript
*
* [142] 環(huán)形鏈表 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if(!head) return null;
let hash = new Map();
while(head) {
if(hash.has(head)) return head;
hash.set(head);
head = head.next;
}
return null;
};
方案二：
/*
* @lc app=leetcode.cn id=142 lang=javascript
*
* [142] 環(huán)形鏈表 II
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if (head === null) {
return null;
}
let slow = head, fast = head;
while (fast !== null) {
slow = slow.next;
if (fast.next !== null) {
fast = fast.next.next;
} else {
return null;
}
if (fast === slow) {
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
};
有兩種方案：1突硝、利用map或set數(shù)據(jù)結(jié)構(gòu)進(jìn)行鏈表的記錄，空間復(fù)雜度為O(N)置济；2解恰、利用快慢指針，計(jì)算相遇的距離浙于，省去了數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間护盈，空間復(fù)雜度為O(1)
2021.05.10
No.143 重排鏈表
給定一個(gè)單鏈表 L：L0→L1→…→Ln-1→Ln ，將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值羞酗，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換腐宋。
示例 1:
給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.
示例 2:
給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reorder-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處胸竞。
方案一：
/*
* @lc app=leetcode.cn id=143 lang=javascript
*
* [143] 重排鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
// 翻轉(zhuǎn)鏈表
const reverseList = head => {
let cur = head;
let pre = null;
while(cur !== null){
let temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
// 分割鏈表
const spliceList = head => {
let dummy = new ListNode(0);
dummy.next = head;
let slow = dummy;
let quick = dummy;
while (quick && quick.next) {
slow = slow.next;
quick = quick.next;
quick = quick.next;
}
let right = slow.next;
slow.next = null;
let left = dummy.next;
return {
left,
right,
dummy
}
}
let { left, right, dummy } = spliceList(head);
right = reverseList(right);
while (left && right) {
let lNext = left.next;
let rNext = right.next;
right.next = left.next;
left.next = right;
left = lNext;
right = rNext;
}
return dummy.next
};
方案二：
/*
* @lc app=leetcode.cn id=143 lang=javascript
*
* [143] 重排鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
let list = []; // 使用數(shù)組存儲(chǔ)鏈表
let node = head; // 使用node遍歷鏈表
// 遍歷鏈表欺嗤，將每個(gè)元素依次存入數(shù)組
while (node) {
list.push(node);
node = node.next;
}
let i = 0; // 使用i指針從頭往后遍歷list
let j = list.length - 1; // 使用j指針從后往前遍歷list
// 兩個(gè)指針向中間推進(jìn)，直到相遇
while (i < j) {
// 將i指向j卫枝，并將i向后移動(dòng)一位
list[i++].next = list[j];
// 將j指向i煎饼，并將j向前移動(dòng)一位
list[j--].next = list[I];
}
// list[i].next需要設(shè)置為null，否則鏈表會(huì)成環(huán)
list[i].next = null;
// head也是新鏈表的頭結(jié)點(diǎn)
return head;
};
有兩種方案：1校赤、快慢指針分割左右鏈表吆玖，利用左右鏈表的插入合成新鏈表；2痒谴、利用數(shù)組的位置進(jìn)行合并處理
2021.05.11
No.148 排序鏈表
給你鏈表的頭結(jié)點(diǎn) head 衰伯，請(qǐng)將其按 升序 排列并返回 排序后的鏈表 。
進(jìn)階：
你可以在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下积蔚，對(duì)鏈表進(jìn)行排序嗎意鲸？
示例 1：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
示例 2：
輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
示例 3：
輸入：head = []
輸出：[]
提示：
鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 5 * 104] 內(nèi)
-105 <= Node.val <= 105
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sort-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)尽爆，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處怎顾。
方案一：
/*
* @lc app=leetcode.cn id=148 lang=javascript
*
* [148] 排序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {
// 鏈表轉(zhuǎn)數(shù)組
const list2Arr = head => {
if(!head) return [];
const a = [head.val];
while(head.next) {a.push(head.next.val);head = head.next;}
return a;
}
// 數(shù)組轉(zhuǎn)鏈表
const arr2List = arr => {
if(arr.length == 0) return null;
let head = new ListNode(arr[0]);
let cur = head;
for(let i=1; i < arr.length; i++) {
cur.next = new ListNode(arr[I]);
cur = cur.next;
};
return head;
};
// 對(duì)數(shù)組重新排序
const sortArr = arr => {
return arr.sort((a,b) => a-b)
}
return arr2List(sortArr(list2Arr(head)))
};
方案二：
/*
* @lc app=leetcode.cn id=148 lang=javascript
*
* [148] 排序鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {
if (!head || !head.next) return head;
let slow = head, fast = head;
let preSlow = null;
while (fast && fast.next) {
preSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
preSlow.next = null;
const l = sortList(head);
const r = sortList(slow);
// 合并鏈表函數(shù)
const merge = (l1, l2) => {
const dummy = new ListNode(0);
let prev = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
if (l1) prev.next = l1;
if (l2) prev.next = l2;
return dummy.next;
};
return merge(l, r);
};
有兩種方案：1、數(shù)組操作漱贱，利用自帶的sort排序槐雾；2、歸并排序幅狮，快慢指針實(shí)現(xiàn)
2021.05.12
No.234 回文鏈表
請(qǐng)判斷一個(gè)鏈表是否為回文鏈表募强。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進(jìn)階：
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有崇摄。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)擎值，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
方案一：
/*
* @lc app=leetcode.cn id=234 lang=javascript
*
* [234] 回文鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
// 翻轉(zhuǎn)鏈表
const reverseList = head => {
let cur=head;
let pre=null;
while(cur !== null){
let temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
// 分割鏈表
const splitList = head => {
let fast = head;
let slow = head;
while (fast.next !== null && fast.next.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
if (head == null) return true;
let l = head;
let _l = reverseList(splitList(head).next);
while( l !== null && _l !== null ) {
if(l.val !== _l.val) {
return false;
}
l = l.next;
_l = _l.next;
}
return true;
};
方案二：
/*
* @lc app=leetcode.cn id=234 lang=javascript
*
* [234] 回文鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
let a='',b='';
while(head!=null){
a=a+head.val;
b=head.val+b;
head=head.next;
}
return a===b;
};
方案三：
/*
* @lc app=leetcode.cn id=234 lang=javascript
*
* [234] 回文鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
const vals = [];
while (head !== null) {
vals.push(head.val);
head = head.next;
}
for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
if (vals[i] !== vals[j]) {
return false;
}
}
return true;
};
有三種方案：1逐抑、利用快慢指針拿到后半段鏈表進(jìn)行翻轉(zhuǎn)比較鸠儿；2、利用js的加號(hào)特性厕氨，實(shí)現(xiàn)了一個(gè)類似棧型的操作进每；3、利用數(shù)組實(shí)現(xiàn)翻轉(zhuǎn)數(shù)組的比較
2021.05.13
No.328 奇偶鏈表
給定一個(gè)單鏈表命斧，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起田晚。請(qǐng)注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性国葬，而不是節(jié)點(diǎn)的值的奇偶性肉瓦。
請(qǐng)嘗試使用原地算法完成遭京。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)泞莉，nodes 為節(jié)點(diǎn)總數(shù)。
示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說明:
應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對(duì)順序船殉。
鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)鲫趁，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推利虫。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/odd-even-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有挨厚。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處糠惫。
方案：
/*
* @lc app=leetcode.cn id=328 lang=javascript
*
* [328] 奇偶鏈表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var oddEvenList = function(head) {
if(!head) return null;
let p = head,
q = head.next,
tmp = q;
while(q && q.next) {
p.next = p.next.next;
q.next = q.next.next;
p = p.next;
q = q.next;
}
p.next = tmp;
return head;
};
利用雙指針進(jìn)行分割處理
總結(jié)：
- 特殊鏈表最常見的方案是快慢指針的進(jìn)行相關(guān)的鏈表查找及處理疫剃，然后根據(jù)特殊鏈表的形式要求進(jìn)行拆分及組合等；
- 也可以使用額外的數(shù)據(jù)結(jié)構(gòu)如棧及hash表等進(jìn)行處理
