fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
双指针技巧秒杀七道链表题目 :: labuladong的算法小抄
大佬，最后一个判断交叉的，当没有交叉时，是不是只要判断p1,p2都已经发生过一次交换后，再出现了需要交换的时候，就可以直接退出了。
func getIntersectionNode(a,b *LinkNode) *LinkNode {
if a == nil || b == nil{
return nil
}
p1, p2 := a, b
tag, tag2 := false, false
for p1.val != p2.val {
if p1.next == nil {
if tag && tag2 {
return nil // 无交叉
}
p1 = b
tag = true
} else {
p1 = p1.next
}
if p2.next == nil {
if tag && tag2 {
return nil // 无交叉
}
p2 = a
tag2 = true
} else {
p2 = p2.next
}
}
return p1 // 返回p1或者p2都可
}
相交链表，大佬这个思路确实巧妙，我想了一个复杂度一样的算法但是更好理解。分别统计两条链表的长度，差值表示非公共部分的长度差，那么让长链表的指针先走差值的步数，再齐头并进，那么如果两个指针相等则是相交的位置。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA, q = headB;
int l1=0, l2=0;
while(p.next!=null){ // 统计A链表长度
p=p.next;
l1++;
}
while(q.next!=null){// 统计B链表长度
q=q.next;
l2++;
}
p = headA;
q = headB;
if(l2>=l1){
for(int i=0;i<l2-l1;i++){
q=q.next;
}
}else{
for(int i=0;i<l1-l2;i++){
p=p.next;
}
}
while(p!=null&&q!=null){
if(p==q){ // 相等说明相交。
return q;
}
p=p.next;
q=q.next;
}
return null;
}
@Clarence-G 这个解法也不错！最后一个 while 循环其实不用那么麻烦，我稍改了下你的代码，你看下：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0, lenB = 0;
// 计算两条链表的长度
for (ListNode p = headA; p != null; p = p.next) {
lenA++;
}
for (ListNode q = headB; q != null; q = q.next) {
lenB++;
}
// 让 p 和 q 到达尾部的距离相同
ListNode p = headA, q = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
p = p.next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
q = q.next;
}
}
// 看两个指针是否会相同，p == q 时有两种情况：
// 1、要么是两条链表不相交，他俩同时走到尾部空指针
// 2、要么是两条链表相交，他俩走到两条链表的相交点
while (p != q) {
p = p.next;
q = q.next;
}
return p;
}
有个疑惑，我想请问下 相交链表的那个如果是这种呢 链表A->B->C->D 和链表F->G->C->H->I呢 也就是相交元素只有C元素，后面的并不是两个链表的公共部分，这样的话用逻辑拼接应该不可行了吧？
相交链表有点问题，如果题目是要求找2个链表的第一个相交点，这种解法才是最优吧；如果只要判断是否相交，感觉可以两个链表分别遍历到头，比较最后一个指针相等就可以了
关于寻找环起点的原理解释还漏了一点，慢指针在进入环之后，慢指针会在一圈内与快指针相遇，这才能证明 k - m 是 head 与环起点的距离。
关于慢指针会在一圈与快指针相遇，通过数学归纳法可证明， a) 快指针与慢指针之间差一步时，继续走，慢指针前进一步，快指针前进2步，两者相遇， b)快指针与慢指针之间差两步时，继续走，慢指针前进一步，快指针前进2步，两者距离差一步，转化为第一种情况 c)快指针之间差N步，继续走，慢指针前进一步，快指针前进两步，两者之间相差N-1步 所以，慢指针要走多少步会相遇？走N次，由于初始距离N必然小于环的周长，所以对于慢指针来说，一圈内就能与快指针相遇
打卡, 判断环那边之前做过一次, 但只想到快慢指针, 快慢指针是用来判断是否存在环的, 但是如何求得环入口结点我一直没搞懂, 然后再看的时候也带有恐惧, 但是玩了半个小时手机, 恐惧心理消失之后, 安下心来看, 一下子看懂了👀, 好文, 好耐下心慢慢看
有个疑惑，我想请问下 相交链表的那个如果是这种呢 链表A->B->C->D 和链表F->G->C->H->I呢 也就是相交元素只有C元素，后面的并不是两个链表的公共部分，这样的话用逻辑拼接应该不可行了吧？
@Money8888 不是，你单链表又不是二叉树，怎么可能C的next会同时有D和H？真的笑到了
相交链表while循环也可以这么写，感觉读起来会简洁一些：
func getIntersectionNode(headA, headB *ListNode) *ListNode {
p1 := headA
p2 := headB
for p1 != nil || p2 != nil {
if p1 == p2 {
return p1
}
if p1 == nil {
p1 = headB
continue
}
if p2 == nil {
p2 = headA
continue
}
p1 = p1.Next
p2 = p2.Next
}
return nil
}
js 版 23. 合并K个升序链表（困难）实现一个优先队列
var mergeKLists = function(lists) {
class PriorityQueue {
constructor(comparator = (a, b) => a > b) {
this._heap = [];
this._comparator = comparator;
}
// 交换节点位置
_swap(i1, i2) {
[this._heap[i1], this._heap[i2]] = [this._heap[i2], this._heap[i1]];
}
_compare(i1, i2) {
return this._comparator(this._heap[i1], this._heap[i2]);
}
// 获得父节点
_parent(i) {
// return (i - 1) >> 1;
return Math.floor((i - 1) / 2);
}
// 获得左节点
_leftChild(i) {
return 2 * i + 1;
}
// 获得右节点
_rightChild(i) {
return 2 * i + 2;
}
// 上移
_shiftUp(index) {
if (index === 0) return;
const parent = this._parent(index);
if (this._heap[parent] && !this._compare(parent, index)) {
this._swap(parent, index);
this._shiftUp(parent);
}
}
// 下移
_shiftDown(index) {
const left = this._leftChild(index);
const right = this._rightChild(index);
if (this._heap[left] && this._compare(left, index)) {
this._swap(left, index);
this._shiftDown(left);
}
if (this._heap[right] && this._compare(right, index)) {
this._swap(right, index);
this._shiftDown(right);
}
}
// 插入
push(value) {
this._heap.push(value);
this._shiftUp(this._heap.length - 1);
}
// 删除堆顶
pop() {
if (this.size() === 1) return this._heap.shift();
const top = this._heap[0];
// pop()方法删除数组最后一个元素并返回，赋值给堆顶
this._heap[0] = this._heap.pop();
// 对堆顶重新排序
this._shiftDown(0);
return top;
}
// 获取堆顶
peek() {
return this._heap[0];
}
// 获取堆的大小
size() {
return this._heap.length;
}
isEmpty() {
return this.size() === 0;
}
}
if (lists.length === 0) return null;
// 虚拟头结点
const dummy = new ListNode(-1);
let p = dummy;
// 优先级队列，最小堆
const pq = new PriorityQueue((a, b) => a.val < b.val);
// 将 k 个链表的头结点加入最小堆
for (const head of lists) {
if (head) pq.push(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
const node = pq.pop();
p.next = node;
if (node.next !== null) {
pq.push(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
};
我用两个链表首尾相连转化为求环形链表起点的问题后，leetCode运行报错了，说改变了链表的结构：Intersected at '4', ERROR: linked structure was modified.
