讨论/《中级算法》 - 相交链表/
《中级算法》 - 相交链表
共 12 个回复
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA;
        ListNode currB = headB;
        int countA = 0;
        int countB = 0;
        while (currA != null) { // 先看两条链表多长
            countA++;
            currA = currA.next;
        }
        while (currB != null) {
            countB++;
            currB = currB.next;
        }
        currA = headA;
        currB = headB;
        for (int i = 0; i < countA - countB; i++) { //让链表长的先走几步,直到剩下一样长
            currA = currA.next;
        }
        for (int i = 0; i < countB - countA; i++) {
            currB = currB.next;
        }
        while (currA != null) { //对比两个链表剩下部分,发现相遇就返回该节点,没有发现就返回null
            if (currA == currB) return currA;
            currA = currA.next;
            currB = currB.next;
        }
        return null;
    }
4
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //相交的 pa+pb = pb+pa
        if(headA == null || headB == null){
            return null;
        }
        ListNode pa = headA;
        ListNode pb = headB;
        while(pa != pb){
            pa = pa == null ? headB:pa.next;
            pb = pb == null ? headA:pb.next;
        }
        return pa; 
    }
}
4

非常巧妙的解法

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA;
        ListNode* b = headB;
        while (a != b)
        {
            a = a != nullptr ? a->next : headB;
            b = b != nullptr ? b->next : headA;
        }
        return a;
    }
};
1

双指针,时间复杂度 O(m+n), 空间复杂度 O(1)

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 用两个指针分别指向 headA 和 headB,一起往后走,则短的那个指针必会先为空
        // 则此时 长的那个指针距离空的位置即为 headA 与 headB 的长度差
        // 再用两个指针指向 headA 和 headB,使长的指针先走完长度差
        // 再让两个指针一起往后走,若两个指针相遇,则为交点,否则无交点
        // time is O(m + n), space is O(1)
        ListNode p = headA;
        ListNode q = headB;
        while (p != null && q != null) {
            p = p.next;
            q = q.next;
        }
        ListNode longer = p == null ? headB : headA;
        ListNode shorter = p == null ? headA : headB;
        ListNode diff = p == null ? q : p;
        while (diff != null) {
            diff = diff.next;
            longer = longer.next;
        }
        while (longer != null) {
            if (longer == shorter) {
                return longer;
            }
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }
1

四种方法带你分析本题

法一:朴素的双指针

求长度差距,而后对齐,再同时前进

普通的对齐双指针法:

//典型双指针问题,先根据两个链表的长度把两个指针所指位置平齐,然后再同时双指针扫描,一旦相等则为交点。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int L1 = getLen(headA);
        int L2 = getLen(headB);
        //双指针平齐
        if(L1>L2){
            int gap = L1-L2;
            for(int i=1;i<=gap;i++)
                headA = headA->next;
        }
        else{
            int gap = L2-L1;
            for(int i = 1;i<=gap;i++)
                headB = headB->next;
        }
        //双指针移动:
        while(headA!=headB){
            headA = headA->next;
            headB = headB->next;
        }
    return headB;
    }
private:
    int getLen(ListNode* head){
        if(head)
            return getLen(head->next)+1;
        else
            return 0;
    }
};

效率尚可
在这里插入图片描述
法二:自己看。。

集合法

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*>check;
        //更新集合
        while(headA){
            check.insert(headA);
            headA = headA->next;
        }
        while(headB){
            if(check.count(headB))
                return headB;
            headB = headB->next;
        }
        return headB;
    }
};

法三:制造闭环

此法较抽象建议查看后面的双指针

成环法(时间复杂度高,但实用性强):

代码


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB)
            return nullptr;
        ListNode* t1 = headA;
        ListNode* t2 = headB;
        while(t1!=t2){
            //如果t1或t2到null了就直接等于头指针(相当于循环)
            //这里判断t1和t2而不是t->next是因为需要经过null状态。
            //要是跳过了null状态,如果两者没有相交则无限循环。
            t1 = t1?t1->next:headA;
            t2 = t2?t2->next:headB;
        }
        return t1;
    }
};

原理解析:

这里图解是跳过了null状态,但是实际不能跳过,加入null状态,也就是在最后多加一个结点即可。
在这里插入图片描述
没错时间复杂度确实是O(n^2)(别看代码简短)
在这里插入图片描述

法四:变相双指针

利用同时行动 且 总距离m+n相等 且 若存在交点则有共同尾部 这几点。

进阶双指针法(利用同时遍历长度相等原理)

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB)
            return nullptr;
        ListNode* t1 = headA;
        ListNode* t2 = headB;
        while(t1!=t2){
            //只需要在成环法的基础上改为遍历到另一个链表
            t1 = t1?t1->next:headB;
            t2 = t2?t2->next:headA;
        }
        return t1;
    }
};

详解
1620744731878.jpg

双指针注意每次移动步数都要一致

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        tailset = set()
        headpointA = headA
        headpointB = headB
        while(headA != None and headB != None):
            if headA == headB:
                return headB
            if headA.next == None:
                tailset.add(headA)
                if len(tailset) == 2:
                    return None
                headA = headpointB#因为下文置next前进了一步,因此A也必须前进一步
                headB = headB.next#置next其实是进了一步,如果不contiue跳出该段循环,则会导致只有一个节点的例子失败
                continue
            if headB.next == None:
                tailset.add(headB)
                if len(tailset) == 2:
                    return None
                headB = headpointA
                headA = headA.next
                continue
            headA = headA.next
            headB = headB.next
        return None

相交链表

  1. 很迷这个输入,样例给的跟参数都不一致,诶,但是不影响做题
  2. 判断链表是否相交,跟链表元素的值val无关,比较时判断指针指向的地址是否是同一个地址即可p == q
  3. 遍历两个链表,获取各自长度,较长的先移动两者相差的长度,借此达到两者能够同时到达末尾,然后两个链表同时移动,如果指针pq同时指向同一个地址p == q,则说明链表相交,否则返回null
  4. 若长度相同,则直接同时移动判断
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int aLength = 0;
        int bLength = 0;
        ListNode *p = headA;
        ListNode *q = headB;
        // 计算链表长度
        while (p != nullptr)
        {
            p = p->next;
            aLength++;
        }
        while (q != nullptr)
        {
            q = q->next;
            bLength++;
        }
        p = headA;
        q = headB;
        // 移动较长指针至 两个链表剩余长度一致
        if (aLength > bLength)
        {
            int differenceLength = aLength - bLength;
            for (int i = 0; i < differenceLength; i++)
            {
                p = p->next;
            }
        }
        else if (aLength < bLength)
        {
            int differenceLength = bLength - aLength;
            for (int i = 0; i < differenceLength; i++)
            {
                q = q->next;
            }
        }
        // 遍历链表 找是否存在相交节点
        while(p != nullptr)
        {
            if(p == q)
            {
                return p;
            }
            p = p->next;
            q = q->next;
        }
        return nullptr;
    }
};

只是值相同,并不是指向同一个地址

代码比较长 思路还算清晰,倒着看两条链表,找到链表长度差,然后让长的先走过长度差,剩下的就好找了,线性时间复杂度,常数空间复杂度,每个链表循环了两遍(或者说不到两遍)

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int longListLen = 0,shortListLen = 0;
        ListNode nodeA = headA, nodeB = headB;
        while (nodeA != null) {
            nodeA = nodeA.next;
            longListLen++;
        }
        while (nodeB != null) {
            nodeB = nodeB.next;
            shortListLen++;
        }
        if (longListLen < shortListLen) {
            ListNode tempNode = headA;
            headA = headB;
            headB = tempNode;
            int tmp = longListLen;
            longListLen = shortListLen;
            shortListLen = tmp;
        }
        for (int i = shortListLen; i < longListLen; i++) {
            headA = headA.next;
        }
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

值相同 不表示节点相同,与值无关的