双指针技巧秒杀七道链表题目 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：双指针技巧秒杀七道链表题目

评论礼仪 见这里，违者直接拉黑。

[MayRay822]

好文

[zy614582280]

打卡刷了两道题

[luckywords]

刚开始写相交链表，写的很多判断条件，最后去理解了一下，还是切换的逻辑上，没想到被绊倒了

[lybxkl]

大佬，最后一个判断交叉的，当没有交叉时，是不是只要判断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都可
}

[GentlemanHao]

刚开始我也是这么写的，这种写法虽然没错，但却有点繁琐
1、不相交的两条链表永远满足循环条件，所以需要加额外的 tag 进行标记；
2、next 先判空才赋值，p1、p2 一定不为空，但有一种情况后判空更好，两条链表都走了自己的又走了对方的，同时指向空，可以直接跳出循环 return null，无需标记了

[Dunzier]

不用判断交换次数的，虽然会有这样的直觉感觉可能会一直遍历下去，但是实际上交换一次以后两个就会同时到达交点或者尾部null节点了， 所以交换一次一定会结束循环， 无需多虑

[Lucas-ljx]

大佬

[Lucas-ljx]

太牛了

[MrXIAGAO]

相交链表的这个技巧太牛了

[javasopp]

讲的真的很不错，我现在能够解答一些类似题目了。。。很开心。谢谢大佬。

[Clarence-G]

相交链表，大佬这个思路确实巧妙，我想了一个复杂度一样的算法但是更好理解。分别统计两条链表的长度，差值表示非公共部分的长度差，那么让长链表的指针先走差值的步数，再齐头并进，那么如果两个指针相等则是相交的位置。

 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;

    }

[Undomiel723]

但是如果两个链表只在头节点相交且他们的长度不相同呢？这种情况是不是不对了

[Zhongjialun744]

同问，如果交点在开头，是否会存在直接移位移过了交点的情况呢

[HzTTT]

交点不可能在头节点吧，因为只能在头节点的下一个交点。你们画一下图就知道你们想的那种情况不可能成立。因为链表不能同时指向两个或以上节点，但是可以同时被两个以上节点指向。

[labuladong]

@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;
}

[Clarence-G]

@labuladong
谢谢大佬，这样确实简单，null值也可以判等，我总是忽略这个条件。

[iMinger]

相交链表，大佬的思路真是清奇，撸完之后爽呆了！

[savvy1st]

东哥，我有点飘了

[Andywjw]

越看越飘

[coder-pig]

妙啊

[Money8888]

有个疑惑，我想请问下 相交链表的那个如果是这种呢 链表A->B->C->D 和链表F->G->C->H->I呢 也就是相交元素只有C元素，后面的并不是两个链表的公共部分，这样的话用逻辑拼接应该不可行了吧？

[wjxiu]

拼起来是这个样子的，不用切换就可以判断了
A->B->C->D F->G->C->H->I
F->G->C->H->I A->B->C->D

[hemw]

哥们，你这是基础不行还是把自己绕进去了？ 你说的这种就不是相交了大哥，两个C只是值相同，next指向都不一样怎么可能是相交节点

[GentlemanHao]

next 只能指向一个

[hihozoo]

相交链表有点问题，如果题目是要求找2个链表的第一个相交点，这种解法才是最优吧；如果只要判断是否相交，感觉可以两个链表分别遍历到头，比较最后一个指针相等就可以了

[Eunice-grow]

啥意思，没懂

[caoyiyang1105]

可以的

[shiboys]

最后一道找交点的题，可以不用算出哪个链表的长短，也不用跳到其他链表。

<T> ListGenericNode<T> getIntersectionNode(ListGenericNode<T> headA, ListGenericNode<T> headB) {
        ListGenericNode<T> shortHead = headA;
        ListGenericNode<T> longHead = headB;
        if (headA == null || headB == null) {
            return null;// 没有相交点
        }
        while (shortHead.next != null && longHead.next != null) {
            shortHead = shortHead.next;
            longHead = longHead.next;
        }
        ListGenericNode<T> pNodeA = headA, pNodeB = headB;
        // 如果 shortHead 链表更长，则 pNodeA 开始迭代
        while (shortHead.next != null) {
            pNodeA = pNodeA.next;
            shortHead = shortHead.next;
        }
        // 如果 longHead 更长，则 pNodeB 开始迭代
        while (longHead.next != null) {
            longHead = longHead.next;
            pNodeB = pNodeB.next;
        }

        // headA is done by shortHeadA point,now start to visit headB
        // and the same as headB if listB is longer than listA
        // 此时 同时 pNodeA 和 pNodeB 开始同时迭代，如果有相交点则如果相加则一定会相交
        while (pNodeA != pNodeB && pNodeA != null) {
            pNodeA = pNodeA.next;
            pNodeB = pNodeB.next;
        }
        return pNodeA;
    }

[StefanJava]

我首先想到的也是先计算两个链表的长度，然后再遍历

[sevenuncler]

虽然也看懂了，但是感觉技巧性还是比较强，能不能总结一些规律、框架啊

[Eunice-grow]

收到

[DreamYuki]

打卡

[DreamYuki]

142. 环形链表 II这题JS用上面的例子解没有做好边界判断，fast.next !== null应该放到while中会更好一些吧

var detectCycle = function(head) {
    if(head === null) {
        return null;
    }
    let fast = head,
        slow = head;
    while(fast !== null) {
        slow = slow.next
        if(fast.next !== null) {
            fast = fast.next.next
        } else {
            return null;
        }
        if(fast === slow) break;
    }
    // 如果遇到空指针说明没有环
    if(fast === null || fast.next === null) {
        return null;
    }
    // slow指回head
    slow = head
    // k次
    while(fast !== slow) {
        slow = slow.next
        fast = fast.next
    }
    return slow
};

[fear666]

两个链表是否相交

东哥的代码执行

a1->a2->c1->c2->null->b1->b2->b3->c1->c2->null
b1->b2->b3->c1->c2->null->a1->a2->c1->c2->null

a1->a2->null->b1->b2->b3->null
b1->b2->b3->null->a1->a2->null

东哥写法的特点

指针走完一个链表后，不是马上就跳到另一个链表的头结点，而是先经过一个null节点

东哥写法的优点

即使两个链表不相交，两个指针最后都必为null，既两个指针相等
利用这个tip 东哥的while语句里面就能写得很简洁，因为不用处理无限循环的情况

[WatsonShum]

求倒数第K个节点的那个题，使用遍历一遍然后在走l-k个节点的方法复杂度和本文中的方法是一样的，都是两个节点总共走了2l-k步。

[lzh2580]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[Eunice-grow]

收到

[Cupcc]

86题分割链表，不需要每次都让链表的next置空，只需要最后添加p2.Next = nil即可。因为在for循环的过程中，每个节点的next都进行了重新分配，只有在最后一个节点next没有重新分配，只需要将最后一个节点的next置空就不会出现环。

func partition(head *ListNode, x int) *ListNode {
// 分成两个链表，提取出小于x的链表
    // less
    dummy1 := &ListNode{-1, nil}
    // greater
    dummy2 := &ListNode{-1, nil}
    p1, p2 := dummy1, dummy2

    p := head
    for p != nil {
        if p.Val < x {
            p1.Next = p
            p1 = p1.Next
        } else {
            p2.Next = p
            p2 = p2.Next
        }
        // 可以不需要
        // temp := p.Next
        // p.Next = nil
        // p = temp
        p = p.Next
    }
    p1.Next = dummy2.Next
    // 出现环的原因在于最后一个节点的指针没有重新分配，可能非空
    p2.Next = nil
    return dummy1.Next
}

[iquping]

第86题可以避免成环

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode current1 = dummy1;
        ListNode current2 = dummy2;
        ListNode temp = head;
        while (temp != null) {
            if (temp.val < x) {
                current1.next = new ListNode(temp.val);
                current1 = current1.next;
            } else {
                current2.next = new ListNode(temp.val);
                current2 = current2.next;
            }
            temp = temp.next;
        }
        current1.next = dummy2.next;
        return dummy1.next;
    }
}

[smallkaka]

打卡，学到了优先级队列的应用👍

[Eunice-grow]

收到

[bLanK-NULL]

厉害了