azl397985856 commented 3 years ago

160. 相交链表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

前置知识

链表

双指针

题目描述

编写一个程序，找到两个单链表相交的起始节点。

yanglr commented 3 years ago

思路

L1和L2的数据举例如下:

L1: 1 -> 2 -> 3 -> 4 -> 5 ->6 L2: 7 -> 4 -> 5 -> 6

接下来，我们来分析这个链表问题，其实所有的链表问题都是玩指针。我们先来看看最容易想到的暴力法求解，然后对其进行改进。

方法1: 暴力法

用两个指针p1, p2，都从头开始走，按题意两指针肯定在某一位置相遇，该方法的时间复杂度为O(m*n)。

p1-双指针分别从头开始遍历

那有没有更快的方法，找到这个点呢？

假如两个链表一样长，那么两个指针同步向前走，第1次汇合时就找到了。

现在遇到的问题是，我们不知道这两个链表的长度，更一般的情形是两个长度不一样，长度差记为 gapLen。此时如果两个指针都从头同步走，必然会丢失一些点，且两指针很有可能无法相遇(错过汇合的那个节点)。那对此有什么办法呢？

方法2: 让较长的链表先走 gapLen 步，接下来两个指针同步向前走

分别遍历1次链表L1 和 L2, 得到长度len1和len2, 记作长度差gapLen = abs(len1 - len2)。

假如我们让较长的链表先走 gapLen 步，接下来两个指针同步向前走，那么在第1次汇合时就能找到了。这就是目前最好的思路了，时间复杂度降为 O(m+n)。

代码(方法2)

实现语言: C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        if (headA == NULL || headB == NULL)
            return NULL;
        int len1 = getLen(headA);
        int len2 = getLen(headB);

        // 较长链表的head指针先移动 gapLen 个位置
        int gap = abs(len1 - len2);
        if (len1 >= len2)
        {            
            while (gap--)
                headA = headA->next;
        }
        else
        {
            while (gap--)
                headB = headB->next;
        }
        // 指针headA 和 headB同步向前移动，遇到相同则直接返回
        while (headA != NULL) {
            if (headA == headB) {
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }

    int getLen(ListNode *head)
    {
        int count = 0;
        ListNode *p = head;
        while (p != NULL)
        {
            count++;
            p = p->next;
        }
        return count;
    }    
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

时间复杂度：O(m+n)
空间复杂度：O(1)

ps: 之前用C# 写了一次这个题的题解, 发表在力扣题解区 .

ysy0707 commented 3 years ago

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode a = headA, b = headB;
        while(a != b){
            a = a == null? headB: a.next;
            b = b == null? headA: b.next;
        }
        return a;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

mmboxmm commented 3 years ago

简答的打个卡吧

代码

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

复杂度分析

Time: O(len(A) + len(B) - len(common(A, B))
Space: O(1)

BpointA commented 3 years ago

思路

暴力法，利用数组求解。用两个数组存储两个链表的节点，再从末尾开始扫描，直到找到不同的值为止。

Python3代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lst1=[]
        lst2=[]
        a=headA
        while a!=None:
            lst1.append(a)
            a=a.next

        b=headB
        while b!=None:
            lst2.append(b)
            b=b.next     
        lst1.reverse()  
        lst2.reverse()
        n=min(len(lst1),len(lst2))
        if lst1[0]!=lst2[0]:
            return None
        for i in range(1,n):
            if lst1[i]!=lst2[i]:
                return lst1[i-1]
        if len(lst1)<len(lst2):
            return lst1[-1]
        else:
            return lst2[-1]

复杂度

时间复杂度：O(m+n)，遍历两次链表，m,n为两个链表的长度

空间复杂度：O(m+n)，构建了两个数组

优化

利用数学推导，可发现在一次遍历，O(1)空间复杂度下完成此题的策略。其逻辑是，当一个结点走到链表终点的时候，将其挪到另一链表起点。这样，二者在相交点时走过的路一样长，可以跳出循环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
       a=headA
       b=headB
       while a!=b:
           if a==None:
               a=headB
           else:
               a=a.next
           if b==None:
               b=headA
           else:
               b=b.next
       return a

BlueRui commented 3 years ago

Problem 160. Intersection of Two Linked Lists

Algorithm

Traverse from the head of two lists, when any one of them reaches the end, continue from the head of the other list.
If there is an intersection, the two traversals will be at the same node at the intersection.
If there is no intersection, both traversal will go over both lists and end at null.

Complexity

Time Complexity: Worst case we need to completely traverse both lists, O(N) where N is the total number of nodes of both lists combined.
Space Complexity: O(1).

Code

Language: Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode curA = headA;
    ListNode curB = headB;
    while (curA != curB) {
        curA = curA == null ? headB : curA.next;
        curB = curB == null ? headA : curB.next;
    }
    return curA;
}

HuijunXu commented 3 years ago


var getIntersectionNode = function(headA, headB) {
    if(!headA||!headB) return null;
    var pa = headA;
    var pb = headB;
    while(pa!==pb){
        pa = pa==null?headB:pa.next;
        pb = pb===null?headA:pb.next
    }
    return pa
};

时间: O(n)

空间: O(1)

zjsuper commented 3 years ago

idea two pointers both iterate A+B or B+A meet at intersect time O(N)

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1 = headA
        p2 = headB
        if headA == headB:
            return headA
        while p1.next:
            p1 = p1.next
            if p2.next:
                p2 = p2.next
            else:
                p2 = headA
        p1 = headB
        if p2.next:
            p2 = p2.next
        else:
            p2 = headA
        if p1 == p2:
            return p1
        while p1.next:
            p1 = p1.next
            if p2.next:
                p2 = p2.next
            else:
                p2 = headA
            if p1 == p2:
                return p1

        return None

yachtcoder commented 3 years ago

Use a set to store the node id of one list then check the other list and return the first one in common. Time O(n+m) Space O(n)

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        ids = set()
        while headA:
            ids.add(id(headA))
            headA = headA.next
        while headB:
            if id(headB) in ids:
                return headB
            headB = headB.next
        return None

O(1) space idea: If two list intersects, they have a common suffix. Assume the longer list have a length of la, the shorter one with a length of lb, then by moving the longer list (la-lb) steps ahead then move the two together, two pointer will meet at the first common node.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        la, lb = 0, 0
        ha, hb = headA, headB
        while headA:
            la += 1
            headA = headA.next
        while headB:
            lb += 1
            headB = headB.next

        headA, headB = ha, hb            
        if la > lb:
            headA, headB = headB, headA

        k = abs(la-lb)
        while k > 0:
            headB = headB.next
            k -= 1
        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

shuichen17 commented 3 years ago

var getIntersectionNode = function(headA, headB) {
    let a = headA;
    let b = headB;
    while (a !== b) {
        if (a === null) {
            a = headB;
        } else {
            a = a.next;
        }
        if (b === null) {
            b = headA;
        } else {
            b = b.next;
        }    
    }
    return a;
};

pophy commented 3 years ago

Intersection of Two Linked Lists

思路

首先判断两个链表是否相交，如果两个表的最后一个Node不一样则不相交
在判断是否相交的同时得到两个链表的长度 l1 和 l2
- k = abs(l1-l2)
长度较长的链表先走k步然后两个链表一起走相同的Node就是相交的点

Java Code

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        int lengthA = 0, lengthB = 0;
        while (curA.next != null) {
            curA = curA.next;
            lengthA++;
        }
        ListNode curB = headB;
        while (curB.next != null) {
            curB = curB.next;
            lengthB++;
        }
        if (curA != curB) {
            return null;
        }
        curA = headA;
        curB = headB;
        int k = Math.abs(lengthA - lengthB);
        if (lengthA > lengthB) {
            for (int i = 0; i < k; i++) {
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < k; i++) {
                curB = curB.next;
            }
        }
        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

时间 & 空间

时间 O(n)
空间 O(1)

a244629128 commented 3 years ago


var getIntersectionNode = function(headA, headB) {
    let fast = headA;
    let slow = headB;

    while(fast !== slow){
        fast = fast.next;
        slow = slow.next;
        if(fast === slow){
            return fast;
        }
        if(fast === null){
            fast = headB;
        }
        if(slow === null){
            slow = headA;
        }

    }
    return fast;
};
// time O(n+m)
//space O(1)

thinkfurther commented 3 years ago

思路

先遍历两个linked list，算出长度。然后长度长的先走长度差点部分，然后一直向前走，直到相遇。

代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA = 0
        curA = headA
        while(curA != None):
            curA = curA.next
            lenA += 1

        lenB = 0
        curB = headB
        while(curB != None):
            curB = curB.next
            lenB += 1            

        curA = headA
        curB = headB

        if(lenA < lenB):
            lenA, lenB = lenB, lenA
            curA, curB = curB, curA

        for _ in range(lenA - lenB):
            curA = curA.next

        while(curA != None):
            if curA ==  curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next

        return None

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

Menglin-l commented 3 years ago

思路：

1.用两个指针分别遍历两条链表，逐一比较，找相同的节点；

2.短的那条会先遍历完，如果没找到，将指针转向长的那条继续遍历；

3.如果有相同节点，返回该节点；如果没有，会一齐指向null，结束while循环，并返回null.

代码部分：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode aPtr = headA;
        ListNode bPtr = headB;

        while (aPtr != bPtr) {

            if (aPtr == null)
                aPtr = headB;
            else 
                aPtr = aPtr.next;

            if (bPtr == null)
                bPtr = headA;
            else 
                bPtr = bPtr.next;

        }
        return aPtr;
    }
}

复杂度：

Time: O(N), 链表A长度+链表B长度

Space: O(1)

JiangyanLiNEU commented 3 years ago

Idea

get the length of A and B
Because the second half is the same, so we move the longer list's pointer forward until their lengths are the same

Update two pointers until they are the same, return the node. Return None if we check all the node and didn't get same address.

Implement (Runtime = O(len(A)+len(B)), Space = O(1) )

class Solution(object):
def getIntersectionNode(self, headA, headB):
    lengthA = 0
    lengthB = 0
    # Get the length of A and B
    cur = headA
    while cur:
        lengthA += 1
        cur = cur.next
    cur = headB
    while cur:
        lengthB += 1
        cur = cur.next
    # Now we know longer list and short list
    minn, maxx = min(lengthA, lengthB), max(lengthA, lengthB)
    if lengthA > lengthB:
        longer = headA
        short = headB
    else:
        longer = headB
        short = headA
    # forward the pointer of longer list, so they have the same length
    for i in range(maxx-minn):
        longer = longer.next
    # check each node, return it if the address is the same
    for i in range(minn):
        if longer == short:
            return longer
        else:
            longer = longer.next
            short = short.next
    # Return null if not intersection
    return None

zhangzz2015 commented 3 years ago

思路

方法1，采用hash set，记录访问的NodeList。检查是否有重复，采用方法，两个List同步访问，并检查，最差情况复杂度为O(n+m)，空间复杂度为O(n+m)
方法2，采用双指针办法，逻辑为ListA走到尾，切换到ListB，ListB走到尾，切换到ListA。最后相同的点就为交叉点。有两种情况，一种是有交叉，一种没有交叉，如果没有交叉，则两个指针都访问了ListA的node和ListB的node，最后相同点为NULL指针，当有交叉点，假设A ---> l +m ， B ---> n +m ，后半部分m 为交叉后相同点，则两个指针每个指针都遍历了 l + n + m，最后第一次相同的点，就为第一个交叉点。时间复杂度，最差情况为O(n+m)，如果是最后一点交叉，空间复杂度为O(1)

关键点

代码

语言支持：C++

C++ Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

     unordered_set<ListNode*> recordNode; 
     while(headA &&headB)
     {
         if(recordNode.find(headA)!=recordNode.end())
             return headA;
         else
             recordNode.insert(headA);
         if(recordNode.find(headB)!=recordNode.end())
             return headB;
         else
             recordNode.insert(headB);
         headA = headA->next;
         headB = headB->next; 
     }
    if(headA)
    {
        while(headA)
        {
           if(recordNode.find(headA)!=recordNode.end())
             return headA;
         else
             recordNode.insert(headA);  
         headA = headA->next;            
        }
    }
    if(headB)
    {
        while(headB)
        {
         if(recordNode.find(headB)!=recordNode.end())
             return headB;
         else
             recordNode.insert(headB);   
         headB = headB->next; 
        }
    }
        return NULL;

    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        // basic rule.  move a move b.  If a == NULL, then move to b head. 
        // if b == NULL, then move to a head. 
        //  same node will be intersection point. 
        ListNode* nodeA = headA; 
        ListNode* nodeB= headB; 
        while(nodeA != nodeB )
        {
            if(nodeA == NULL )
            {
                nodeA = headB;
            }
            else
                nodeA = nodeA->next; 

            if(nodeB == NULL)
            {
                nodeB = headA;
            }
            else
                nodeB = nodeB->next; 
        }

        return nodeA; 

    }
};

leungogogo commented 3 years ago

LC160. Intersection of Two Linked Lists

Method 1. Hash

Main Idea

First traverse list A and use a hash set to record visited, then traverse B, the first node of visited node will be the intersection, if there's no such a node, that means no intersection.

Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        while (headA != null) {
            visited.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (visited.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

Complexity Analysis

Time: O(m + n)

Space: O(m)

Method 2. Two Pointers

Main Idea

First traverse both arrays to find their lengths, then use two pointers pA and pB to traverse both lists. Before we start tracersal, move the pointer of the longer list forward by abs(lA-lB).

Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = listLen(headA), lenB = listLen(headB), diff = Math.abs(lenA - lenB);
        ListNode cur1 = lenA < lenB ? headB : headA;
        ListNode cur2 = lenA < lenB ? headA : headB;
        for (int i = 0; i < diff; ++i) {
            cur1 = cur1.next;
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                return cur1;
            } else {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return null;
    }

    private int listLen(ListNode head) {
        if (head == null) {
            return 0;
        }
        return 1 + listLen(head.next);
    }
}

Complexity Analysis

Time: O(m + n)

Space: O(1)

nonevsnull commented 3 years ago

思路

拿到题的直觉解法

两个LinkedList如果长度一样，那么直接遍历就好；

两个LinkedList如果长度不同，则先算长短，然后长的先走length的差，就可以齐头并进当作相同长度的case处理；

AC

稍微优化

两个LinkedList不用分别求长度，要知道的只是长度差. 更进一步，连长度差都不需要知道，只需要长的先走diff那几步，所以可以稍微优化一下这部分。复杂度没变。

AC

代码


//遍历两次求长度
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = 0;
        ListNode curA = headA;
        while(curA != null){
            curA = curA.next;
            lengthA++;
        }
        int lengthB = 0;
        ListNode curB = headB;
        while(curB != null){
            curB = curB.next;
            lengthB++;
        }

        ListNode headLong = lengthA >= lengthB?headA: headB;
        ListNode headShort = lengthA >= lengthB?headB: headA;
        int diff = Math.abs(lengthA - lengthB);

        while(diff > 0){
            headLong = headLong.next;
            diff--;
        }

        while(headLong != headShort){
            headLong = headLong.next;
            headShort = headShort.next;
        }

        return headLong;
    }
}

//遍历一次
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA != null && curB != null){
            curA = curA.next;
            curB = curB.next;
        }

        ListNode shortee = curA == null?headA: headB;
        ListNode longee = curA == null?headB: headA;
        ListNode running = curA == null?curB: curA;

        int diff = 0;
        while(running != null){
            running = running.next;
            longee = longee.next;
        }
        while(shortee != null && longee != null && shortee != longee){
            shortee = shortee.next;
            longee = longee.next;
        }
        return shortee;
    }
}

复杂

两个解法复杂度一样，但是第二个方法因为少遍历了一些所以稍微优化点； time: O(N) space: O(1)

leo173701 commented 3 years ago

要点：双指针，链表的拼接思路：可以这么理解，a，b两个链表，变更为 a+b 和 b+a，长度就相等了，然后等步遍历判断是否相等就行了时间复杂度: O(m+n) 空间复杂度: O(1)

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        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;
    }

ginnydyy commented 3 years ago

Problem

https://leetcode.com/problems/intersection-of-two-linked-lists/

Notes

Can solve this problem by using set or two pointers
- Use set
- Scan one list and record the nodes in a set
- Scan the other list and compare the nodes to the set
- Use two pointers
- Two p1, p2 traverse two lists respectively
- When p1 reaches the end of listA, point to the head of listB, and continue
- When p2 reaches the end of listB, point to the head of listA, and continue
- When p1 == p2, stop the traversal, and return p1 as the result
- When there is an intersection, p1 != null
  - listA is A+C; listB is B+C (start of C is the intersection)
  - p1 goes through A+C+B+C
  - p2 goes through B+C+A+C
  - p1 p2 stop at the second time they reach the start of C
- When there is no intersection, p1 == null (at this point, p1 and p2 stop at the end of both lists)
  - listA is A+C; listB is B+D (there is no intersection)
  - p1 goes through A+C+B+D
  - p2 goes through B+D+A+C
  - p1 reaches the end of D while p2 reaches the end of C, they both are null at this point, p1 == p2, so the traversal stops

Solution

Use set

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // scan one list and record nodes in a set
    // scan the other list and compare to the set
    Set<ListNode> set = new HashSet<>();
    while(headA != null){
        set.add(headA);
        headA = headA.next;
    }
    while(headB != null){
        if(set.contains(headB)){
            return headB;
        }
        headB = headB.next;
    }

    return null;
}
}

Use two pointers

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // two pointers to traverse two list
    // when p1 reaches the end of listA, point to head of listB
    // when p2 reachese the end of listB, point to head of listA
    // the traversal stops when p1 == p2, p1 is the result
    // when there is an intersection, p1 != null
    // when there is no intersection, p1 == null (p1 p2 stop at the end of both lists)
    ListNode p1 = headA;
    ListNode p2 = headB;
    while(p1 != p2){
        p1 = p1 == null? headB: p1.next;
        p2 = p2 == null? headA: p2.next;
    }
    return p1;
}
}

Complexity

Use set
- Time: O(m + n) (m is the size of listA, n is the size of listB).
- Space: O(m) to store the nodes of listA.
Use two pointers
- Time: O(m + n).
- Space: O(1).

biancaone commented 3 years ago

思路 🏷️

追及问题，如果有相交，那么遇到的那一刻，走过的路程应该是一样的。

代码 📜

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        p1 = headA
        p2 = headB

        while p1 != p2:
            if p1:
                p1 = p1.next
            else:
                p1 = headB

            if p2:
                p2 = p2.next
            else:
                p2 = headA

        return p1

复杂度 📦

时间复杂度 O(n)
空间复杂度 O(1)

laofuWF commented 3 years ago

💻Code:

# find the middle value of given list
# create a root with that value
# recursively find its left part middle value and right part middle value
# time/space: O(N)
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head: return head

        prev, slow, fast = None, head, head

        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next

        if prev: 
            prev.next = None

        root = TreeNode(slow.val)

        if slow == fast: 
            return root

        left = head
        right = slow.next

        root.left = self.sortedListToBST(left)
        root.right = self.sortedListToBST(right)

        return root

falconruo commented 3 years ago

思路: 比较两个链表是否有交叉结点，定义两个指针p, q分别指向headA, headB

首先计算每个链表的结点个数，存入变量lenA, lenB，如果任意一个链表为空则无交叉，返回nullptr
令p指向结点数多的链表, q指向结点数少的链表, 令两个链表的长度差为diff
- 首先移动长的链表直至diff为0
- 同时移动两个链表，并判断结点是否相等，相等则说明是交叉结点并返回当前结点，不等则继续指向下一个结点，直至表尾
如果没有交叉(intersection)返回nullptr

复杂度分析:

时间复杂度: O(n + m), n, m为给定链表A和B长度
空间复杂度: O(1)

代码(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA, *pB = headB;
        while(pA != pB){
            pA = pA ? pA->next : headB;
            pB = pB ? pB->next : headA;
        }
        return pA;
    }
};

wangzehan123 commented 3 years ago

题目地址(160. 相交链表)

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

 

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

 

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

前置知识

公司

暂无

思路

关键点

代码

语言支持：Java

Java Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
        // Note: In the case lists do not intersect, the pointers for A and B
        // will still line up in the 2nd iteration, just that here won't be
        // a common node down the list and both will reach their respective ends
        // at the same time. So pA will be NULL in that case.
}
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

chenming-cao commented 3 years ago

解题思路

方法参考链表讲义

方法1：双指针，最开始分别指向headA和headB，当指针走到终点的时候，更新指针指向另外链表的head。当两个指针指向的节点相同时，即找到交叉节点。此时指针走过了两个链表不相同的部分各一次，并且走过了一次两个链表相同部分，走的距离相等。

方法2：哈希表，先遍历链表A，将节点存到哈希表中，再遍历链表B，找到第一个哈希表中出现的节点即为交叉节点。

代码

方法1：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = a != null ? a.next : null;
            b = b != null ? b.next : null;
            if (a == null && b == null) return null;
            if (a == null) a = headB;
            if (b == null) b = headA;
        }
         return a;
    }
}

复杂度分析

时间复杂度：O(m+n)
空间复杂度：O(1)

方法2：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodes = new HashSet<>();
        ListNode a = headA;
        ListNode b = headB;

        while (a != null) {
            nodes.add(a);
            a = a.next;
        }

        while (b != null) {
            if (nodes.contains(b)) return b;
            b = b.next;
        }
        return null;
    }
}

复杂度分析

时间复杂度：O(m+n)
空间复杂度：O(m)，建立了哈希表储存A中所有节点

littlemoon-zh commented 3 years ago

day 10

160. Intersection of Two Linked Lists

简单的思路是用Set；

O(1) space的思路是，先找两个链表的长度差diff，然后让长的那个先走diff步，接着两个同时走，如果途中有相等，说明遇到重合节点；

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;

        while (a != null && b != null) {
            a = a.next;
            b = b.next;
        }

        int diff = 0;

        if (b != null) {
            a = b;
            ListNode t = headA;
            headA = headB;
            headB = t;
        }

        while (a != null) {
            a = a.next;
            diff++;
        }

        a = headA;
        b = headB;

        while (diff-- > 0) {
            a = a.next;
        }
        while (a != null && b != null) {
            if (a == b)
                return a;
            a = a.next;
            b = b.next;
        }

        return null;       
    }
}

xj-yan commented 3 years ago

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curtA = headA, curtB = headB;
        while (curtA != curtB){
            curtA = curtA == null ? headB : curtA.next;
            curtB = curtB == null ? headA : curtB.next;
        }
        return curtA;
    }
}

Time Complexity: O(n), Space Complexity: O(1)

skinnyh commented 3 years ago

Note

Use two pointers moving from the heads of two list. Quit iteration when the two pointers meet. When each pointer reaches to at the end, move it to the other head so it solves the problem of length difference.
When two lists have the same length, two pointers will reach the end the same time on the first iteration if no intersect and we can end there when both pointers are None.

Solution

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pa, pb = headA, headB
        while (pa != pb):
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        return pa

Time complexity: O(m+n)

Space complexity: O(1)

LAGRANGIST commented 3 years ago

题目描述

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

思路

两个长度分别为a, b则长的那一个链表先走abs(a-b)步
然后两个一起走就会相遇在相交的地方

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getListLength(ListNode *head)
    {
        if(!head)
        {
            return 0;
        }

        int cnt = 0;

        while(head)
        {
            cnt++;
            head = head -> next;
        }
        return cnt;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = getListLength(headA);
        int lenB = getListLength(headB);
        ListNode *longer = (lenA>=lenB)? headA:headB;
        ListNode *shorter = (longer == headA)?headB:headA;
        int gap = lenA>lenB?(lenA-lenB):(lenB-lenA);
        for(int i = 0;i<gap;i++)
        {
            longer = longer->next;
        }
        while(longer!=shorter)
        {
            longer = longer->next;
            shorter = shorter -> next;
        }
        return longer;
    }
};

复杂度

时间复杂度 O(n)
空间复杂度 O(1)

Yufanzh commented 3 years ago

Intuition

For linked list, double pointers are always a common trick The critical part is headA and headB doesn't necessarily meet at intersection after same steps One way to do it is to tranverse headA to headB, and then tranverse headB to headA, then their intersection will both appear in the end (or as nullptr)

Algorithm in Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1 = headA
        p2 = headB
        while p1 != p2:
            if p1 == None:
                p1 = headB
            else:
                p1 = p1.next
            if p2 == None:
                p2 = headA
            else:
                p2 = p2.next
        return p1

Complexity Analysis:

Time complexity: O(N) where n is the sum length of headA and headB
Space complexity: O(1)

zol013 commented 3 years ago

思路：使用两个指针放在headA和headB，当指针是链表尾部的时候重置指针到另一链表的头部，两个指针相遇的点即是交点 Python 3 Code:

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

Time Complexity: O(N + M) in the worst case where there is not intersection, we need to traverse the two linked lists. Space Complexity: O(1)

zhiyuanpeng commented 3 years ago

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        pa = headA
        pb = headB
        while pa != pb:
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next
        return pa

time complexity O(m+n) space comoplexity 'O(1)'

kidexp commented 3 years ago

thoughts

l两个指针，跑到a的尽头走b，走到b的尽头走a，走完a和b之后一定会会在节点相遇，如果第二遍走到尽头不相遇就是没有交点

code

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1, l2 = headA, headB
        finish = False
        while l1 != l2:
            if l1.next is None and l2.next is None:
                if finish:
                    return None
            if l1.next is None:
                l1 = headB
                finish = True
            else:
                l1 = l1.next
            if l2.next is None:
                l2 = headA
            else:
                l2 = l2.next
        return l1

complexity

time complexity O(m+n) space complexity O(1)

itsjacob commented 3 years ago

Intuition

Easy solution with O(n) space is to create a dictionary for one list and check the existance of each node in the other list
O(1) space complexity solution is recognizing that the interection problem in linked list is often associated with two pointers meet problem: can be with different walking paces pointers but same walking distances, or different intial walking distance walkers but with same walking paces, like in this case
The stop condition for this type of problem is 'WHEN THEY MEET': either meet at interection or the end of their lists (nullptr)
The type of problem often comes with resetting the pointer to heads of lists when it first reaches the tail of the list

Implementation

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
  {
    // O(n) time and O(1) space complexities
    // fast/slow two-pointer problem, actually same pace but different distance walkers
    // The first time two pointers will meet is when they walk the same amount of distance
    // Walker A walked lengthA = skipA + commonLen, after it reaches the end of list A
    // Walker B walked lengthB = skipB + commonLen, after it reaches the end of list B
    // If walker A walks additional skipB, and walker B walks additional skipA,
    // they will have their first meet at the total distance skipA + commonLen + skipB
    // The the trick is walking both pointers at the same pace, until their first meet if they can meet,
    // otherwise, they will all end up with nullptr at the end of their lists
    ListNode *pA{ headA };
    ListNode *pB{ headB };
    while (pA != pB) {
      // walk another skipB for walker A
      if (pA == nullptr)
        pA = headB;
      else
        pA = pA->next;
      // walk another skipA for walker B
      if (pB == nullptr)
        pB = headA;
      else
        pB = pB->next;
    }
    return pA;
  }
};

Complexity

Time complexity: O(N)
Space complexity: O(1)

tongxw commented 3 years ago

思路

遍历链表A，节点存到集合里。遍历链表B，如果某个节点在集合里，就返回。

代码

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
  let setA = new Set();
  let p = headA;
  while (p !== null) {
    setA.add(p);
    p = p.next;
  }

  p = headB;
  while (p !== null) {
    if (setA.has(p)) {
      return p;
    }
    p = p.next;
  }

  return null;
  // return trick(headA, headB);
};

TC: O(len(headA) + len(headB)) SC: O(len(headA))

james20141606 commented 3 years ago

Day 10 160. Intersection of Two Linked Lists (linked list, two pointers)

Problem Link
- 160. Intersection of Two Linked Lists
Ideas
- A naive solution is to use hash table to store the nodes in A. Then if we find a node in B is contained in set A we could return the node. Complexity: Time: O(N), Space: O(N)
- O(1) space solution. The tricky part is we could use two pointers, starting from head A and head B correspondingly. Then when the pointers reach the end, start from the other list's head. This will make sure they travel same distance when they meet at the intersection. Complexity: Time: O(N), Space: O(1)
Complexity:
- Time: O(N)
- Space: O(1)
Code

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A = headA
        B = headB
        while A != B:
            A = A.next if A  else headB
            B = B.next if B  else headA
        return A

other resources:

st2yang commented 3 years ago

思路

双指针

代码

python

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    pA = headA
    pB = headB

    while pA != pB:
        if not pA:
            pA = headB
        else:
            pA = pA.next
        if not pB:
            pB = headA
        else:
            pB = pB.next

    return pA

复杂度

时间: O(m + n)
空间: O(1)

RocJeMaintiendrai commented 3 years ago

题目

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路

使用两个索引a和b，假设两个链表不相交的部分长度各是a和b，相交后的长度为c，那么索引a走到尾部后从headB再走，b也走到尾部后从headA走，那么都走了a + b + c的距离，因此如果有相交时a，b皆不为null。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while(a != b) {
            if(a == null) {
                a = headB;
            } else {
                a = a.next;
            }
            if(b == null) {
                b = headA;
            } else {
                b =b.next;
            }
        }
        return a;
    }
}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(1)

Mahalasu commented 3 years ago

思路

分别遍历两个链表，两个指针同时向后移动。当ptr1为空则跳到headB，同样ptr2为空则跳到headA，当两者相等时则返回此时的结点；不然则当两者都为空时，返回None。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        ptr1 = headA
        ptr2 = headB

        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next

            if not ptr1 and not ptr2:
                return None

            if not ptr1:
                ptr1 = headB
            if not ptr2:
                ptr2 = headA

        return ptr1

T: O(m + n) S: O(1)

naivecoder-irl commented 3 years ago

思路

设置双指针pA和pB，pA走过的路径为A链+B链

pB走过的路径为B链+A链

pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。

pA, pB指针相遇的点为相交的起始节点，否则没有相交点

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

复杂度分析

时间复杂度：时间复杂度为O(m+n)，分别为headA和headB的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
空间复杂度：未使用额外的空间，空间复杂度O(1)

carsonlin9996 commented 3 years ago

判断两个链表的长度，先让长的链表走长度的区别
然后指针同时一步步遍历，直到找到相同的点

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    int lenA = getLength(headA);
    int lenB = getLength(headB);

    ListNode ptrA = headA;
    ListNode ptrB = headB;

    int diffStep = Math.abs(lenA - lenB);

    if (lenA > lenB) {
        while (diffStep > 0) {
            ptrA = ptrA.next;
            diffStep--;
        }
    } else {
        while (diffStep > 0) {
            ptrB = ptrB.next;
            diffStep--;
        }
    }

    while (ptrA != ptrB) {
        ptrA = ptrA.next;
        ptrB = ptrB.next;
    }
    return ptrA;

}

public int getLength(ListNode node) {

    if (node == null) {
        return 0;
    }

    int length = 1;

    while (node.next != null) {
        node = node.next;
        length++;
    }

    return length;
}

}

leige635539766 commented 3 years ago

思路

看两个链条相交的节点

时间复杂度

O(N)

代码

class Solution:
    def getNode(self, A, B):
        Ha, Hb =A,B
        while Ha != Hb:
            Ha = Ha.next if Ha else B
            Hb = Hb.next if Hb else A
        return Ha

siyuelee commented 3 years ago

1.

use hash table to keep the nodes in A. Then there is a node in B is contained in hash table we could return the node.

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        seen = dict()
        cur = headA
        while cur:
            seen[cur] = 1
            cur = cur.next

        cur = headB
        while cur:
            if cur in seen:
                return cur
            cur = cur.next
        return None

Complexity: Time: O(N), Space: O(N)

2.

two pointers - starting from head A and head B. Then when the pointers reach the end, start from the other list's head. They travel same distance when they meet at the intersection. If they don't meet, pointer A and pointer B will both point Null.

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB: return None

        # 2 pointers
        pa = headA
        pb = headB
        while pa != pb:
            pa = headB if not pa else pa.next
            pb = headA if not pb else pb.next
        return pa

Complexity: Time: O(N), Space: O(1)

pan-qin commented 3 years ago

idea: use a hashtable to store listnode in A. iterate through B to find the one that exist in A. Time: O(m+n) Space: O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        HashSet<ListNode> listA = new HashSet<>();
        ListNode curr=headA;
        while(curr!=null) {
            listA.add(curr);
            curr=curr.next;
        }
        curr=headB;
        while(curr!= null) {
            if(listA.contains(curr)) {
                return curr;
            }
            curr=curr.next;
        }
        return null;
    }
}

yan0327 commented 3 years ago

思路：自己写了一个方法，首先遍历两个链表的长度。通过判断最后一个节点是否为同一个节点来判断两个链表是否相交。但是这里没必要，因为要找第一个相交节点。于是取差值，让长链表先走差值。然后两个链表同时走，关键是判断当前链表是否为nil，否则同时向后移。若遍历完差值没发现相交点，则两个链表不相交

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil{
        return nil
    }
    num1 := count(headA)
    num2 := count(headB)
    gab := abs(num1 - num2)
       if num1 > num2{
           for gab >0{
               headA = headA.Next
               gab--
           }
       }else{
           for gab > 0{
               headB = headB.Next
               gab--
           }  
       }

   for headA != nil {
       if headA == headB{
           return headA
       }
       headA = headA.Next
       headB = headB.Next
   }
   return nil
}

func count (head *ListNode) int{
    sum := 0
    p := head
    for p != nil{
        p = p.Next
        sum++
    }
    return sum
}

func abs(x int) int{
    if x < 0 {
        return -x
    }else{
        return x
    }
}

时间复杂度：O(n+m) 空间复杂度：O（1）

qyw-wqy commented 3 years ago

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }
}

Time: O(n) Space: O(1)

suukii commented 3 years ago

Link to LeetCode Problem

S1: 暴力法

对链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。

/**
 * 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;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode *pA = headA;

        while (pA != NULL) {
            ListNode *pB = headB;
            while (pB != NULL) {
                if (pA == pB) {
                    return pA;
                }
                pB = pB->next;
            }
            pA = pA->next;
        }
        return NULL;
    }
};

Time: $O(m*n)$，m 和 n 分别是两个链表的长度。
Space: $O(1)$

S2: 哈希表

先遍历遍历链表 A，将所有节点都存在一个哈希表中
再遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

/**
 * 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;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;
        ListNode* p = headA;
        while (p != NULL) {
            visited.insert(p);
            p = p->next;
        }
        p = headB;
        while (p != NULL) {
            if (visited.find(p) != visited.end()) return *visited.find(p);
            p = p->next;
        }
        return NULL;
    }
};

Time: $O(m+n)$，m 和 n 分别是两个链表的长度。
Space: $O(m)$

S3: 双指针

如果两个链表有交点的话：

如果链表没有交点的话：

两个链表长度一样时，第一次遍历结束后 pA 和 pB 都是 null，结束遍历。
两个链表长度不一样时，两次遍历结束后 pA 和 pB 都是 null，结束遍历。

/**
 * 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;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == NULL ? headB : pA->next;
            pB = pB == NULL ? headA : pB->next;
        }
        return pA;
    }
};

Time: $O(m+n)$，m 和 n 分别是两个链表的长度。
Space: $O(1)$

xiezhengyun commented 3 years ago

思路

这题我做过

循环两个链表，一个完了接着另一个，这样，两个指针就是走了相同的路，他们会同时到达相交节点，或者同时等于null

/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
var p1 = headA,p2 = headB;
while(p1 !== p2){
p1 = p1 ? p1.next: headB
p2 = p2 ? p2.next: headA
}
return p1 
};

复杂度

M，N为2个链表的长度

Time：O(M+N)
Space: O(1)

lilixikun commented 3 years ago

思路

方法一：用Hash表做标记、这里不多说

方法二：双指针、两个链表首尾连着、如果有相交一定会相遇

代码


var getIntersectionNode = function(headA, headB) {
let p1 = headA,p2 = headB
while(p1!=p2){
    p1=p1?p1.next:headB
    p2=p2?p2.next:headA
}
return p1
};
``
# 复杂度

时间复杂度：O（m+n）
空间复杂福：O（1）

chakochako commented 3 years ago

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        d = dict()
        while headA:
            d[headA] = 1
            headA = headA.next
        while headB:
            if d.get(headB):
                return headB
            else:
                headB = headB.next
        return None

ccslience commented 3 years ago

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

时间复杂度: O(N)，空间复杂度：O(1)

leetcode-pp / 91alg-5-daily-check

【Day 10 】2021-09-19 - 160. 相交链表 #25

160. 相交链表

入选理由

题目地址

前置知识

题目描述

思路

方法1: 暴力法

方法2: 让较长的链表先走 gapLen 步，接下来两个指针同步向前走

代码(方法2)

实现语言: C++

复杂度分析

代码

复杂度分析

思路

Python3代码

复杂度

优化

Problem 160. Intersection of Two Linked Lists

Algorithm

Complexity

Code

时间: O(n)

空间: O(1)

Intersection of Two Linked Lists

思路

时间 & 空间

思路

代码

复杂度

思路：

1.用两个指针分别遍历两条链表，逐一比较，找相同的节点；

2.短的那条会先遍历完，如果没找到，将指针转向长的那条继续遍历；

3.如果有相同节点，返回该节点；如果没有，会一齐指向null，结束while循环，并返回null.

代码部分：

复杂度：

Time: O(N), 链表A长度+链表B长度

Space: O(1)

Idea

Implement (Runtime = O(len(A)+len(B)), Space = O(1) )

思路

关键点

代码

LC160. Intersection of Two Linked Lists

Method 1. Hash

Main Idea

Code

Complexity Analysis

Method 2. Two Pointers

Main Idea

Code

Complexity Analysis

思路

代码

复杂

Problem

Notes

Solution

Complexity

思路 🏷️

代码 📜

复杂度 📦

💻Code:

题目地址(160. 相交链表)

题目描述

前置知识

公司

思路

关键点

代码

解题思路

代码

day 10

Note

Solution

题目描述

160. 相交链表

思路

代码