链表
【LeetCode 直通车】：234 回文链表（简单）
- 我们遍历出数组后将其反转对比即可
javascript
/**
* 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 arr = [];
let cur = head;
while(cur) {
arr.push(cur.val);
cur = cur.next;
}
let arr1 = arr.slice().reverse();
return arr.join('') === arr1.join('')
};- 获取后使用双指针
javascript
var isPalindrome = function (head) {
const arr = [];
let cur = head;
while (cur) {
arr.push(cur.val);
cur = cur.next;
}
let left = 0, right = arr.length -1;
while(left < right) {
if(arr[left] !== arr[right]) return false;
left++;
right--;
}
return true
};- 直接反转链表后进行比较
javascript
/**
* 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 copyList = (list) => {
let cur = list
let dummy = new ListNode();
let curnode = dummy;
while(cur) {
curnode.next = new ListNode(cur.val, cur.next);
cur = cur.next;
curnode = curnode.next;
}
return dummy.next;
}
const reverseList = (list) => {
let dummy = list;
let pre = null;
let cur = dummy;
while(cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next
}
return pre;
}
const copylist = copyList(head);
const reverselist = reverseList(head);
let l1 = copylist, l2 = reverselist;
while(l1 && l2) {
if(l1.val !== l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true
};- 快慢指针 反转 slow 后面的 链表与之前的对比即可 边界处理 奇偶问题
javascript
/**
* 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 slow = head, fast= head, l1 = head;
while(fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
};
let l2 = reverseList(slow.next);
while(l2) {
if(l1.val !== l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true
};
const reverseList = (list) => {
let pre = null, cur = list;
while(cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre
}👉 【LeetCode 直通车】：206 反转链表（简单）
这个在上面已经用到了， 就是借助中间变量 pre 以及 cur 来进行实现
javascript
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let cur = head;
let pre = null;
while(cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next
}
return pre;
};👉 【LeetCode 直通车】：141 环形链表（简单）
环形列表使用快慢指针， 如果是环形那么他们一定会相遇
javascript
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let slow = head, fast = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast) return true;
}
return false
};把我笑死的解法
JSON.stringify(head) 秒杀法😃 除非不报错，报错就是有环！！
javascript
var hasCycle = function (head) {
try {
JSON.stringify(head)
} catch{
return true
}
return false
};👉 【LeetCode 直通车】：160 相交链表（简单）
链表🍌的逻辑就是 p1 +p2 = p2 + p1 所以所以让 p1 走完走p2的路即可 相等🐔🍌
javascript
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let l1 = headA, l2 = headB;
while(l1 !== l2) {
l1 = l1 ? l1.next : headB;
l2 = l2 ? l2.next : headA;
}
return l1
};合并两个有序链表
javascript
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
let list = new ListNode();
let dummy = list;
let l1 = list1, l2 = list2;
while(l1&&l2) {
if(l1.val < l2.val) {
dummy.next = l1;
l1 = l1.next
} else {
dummy.next = l2;
l2 = l2.next
}
dummy = dummy.next;
}
dummy.next = l1 ?? l2;
return list.next;
};👉 【LeetCode 直通车】：148 排序链表（中等）
合并有序最终可排序 所以将链表拆分成最小单位 1 然后进行合并即可
javascript
var mergeTwoLists = function(list1, list2) {
let dummyHead = new ListNode();
let l1 = list1, l2 =list2, dummy = dummyHead;
while(l1 && l2) {
if(l1.val < l2.val) {
dummy.next = l1;
l1 = l1.next
} else {
dummy.next = l2;
l2 = l2.next;
}
dummy = dummy.next;
}
dummy.next = l1 ?? l2;
return dummyHead.next
};
const getHead = (subLength, curr) => {
let head = curr;
for (let i = 1; i < subLength && curr && curr.next; i++) {
curr = curr.next;
}
let nextHead = null;
if (curr !== null) {
nextHead = curr.next;
curr.next = null;
}
return [head, nextHead]
}
var sortList = function (head) {
if (!head) return head;
let length = 0;
let node = head;
while (node) {
length++;
node = node.next;
}
const dummyHead = new ListNode(0, head);
for (let subLength = 1; subLength < length; subLength <<= 1) {
let prev = dummyHead, curr = dummyHead.next;
while (curr !== null) {
let head1, head2, nextHead;
[head1, nextHead] = getHead(subLength, curr)
curr = nextHead;
[head2, nextHead] = getHead(subLength, curr);
curr = nextHead;
const merged = mergeTwoLists(head1, head2);
prev.next = merged;
while (prev.next !== null) {
prev = prev.next;
}
}
}
return dummyHead.next;
};👉 【LeetCode 直通车】：23 合并K个升序链表（困难）
分治 或者两辆合并即可
javascript
/**
* 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) {
if(!lists.length) return null
while(lists.length>1) {
lists[0] = merge(lists[0], lists[1]);
lists.splice(1,1,)
}
return lists[0]
};
const merge = (list1, list2) => {
const dummyHead = new ListNode();
let dummy = dummyHead, l1 = list1, l2 = list2;
while(l1 && l2) {
if(l1.val < l2.val) {
dummy.next = l1;
l1 = l1.next
} else {
dummy.next = l2;
l2 = l2.next;
}
dummy = dummy.next
}
dummy.next = l1 ?? l2;
return dummyHead.next;
}
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 合并从 lists[i] 到 lists[j-1] 的链表
function dfs(i, j) {
const m = j - i;
if (m === 0) return null; // 注意输入的 lists 可能是空的
if (m === 1) return lists[i]; // 无需合并，直接返回
const left = dfs(i, i + (m >> 1)); // 合并左半部分
const right = dfs(i + (m >> 1), j); // 合并右半部分
return merge(left, right); // 最后把左半和右半合并
}
return dfs(0, lists.length);
};👉 【LeetCode 直通车】：25 K 个一组翻转链表（困难）
javascript
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
const dummyHead = new ListNode(0, head);
let pre = dummyHead;
while(head) {
let tail = pre;
for(let i = 0; i < k; i++) {
tail = tail.next;
if(!tail) {
return dummyHead.next;
}
}
const next = tail.next;
[head, tail] = reverseList(head, tail);
pre.next = head;
tail.next = next;
pre = tail;
head = tail.next;
}
return dummyHead.next;
};
const reverseList = (head, tail) => {
let pre = tail.next;
let cur = head;
while(pre !== tail) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return [tail, head]
}