azl397985856 commented 2 years ago

160. 相交链表

入选理由

暂无

题目地址

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

前置知识

链表

双指针

题目描述


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

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


![](https://tva1.sinaimg.cn/large/008i3skNly1gul6frn1lsj30km06pglt.jpg)

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

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

示例 1：


![](https://tva1.sinaimg.cn/large/008i3skNly1gul6g0cmpej60km06pgls02.jpg)

输入：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：


![](https://tva1.sinaimg.cn/large/008i3skNly1gul6gcen03j60ha06p0st02.jpg)

输入：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：


![](https://tva1.sinaimg.cn/large/008i3skNly1gul6gprq2vj60am06p3yi02.jpg)

输入：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) 内存的解决方案？

qibao1112 commented 2 years ago

思路

使用hashMap集合，遍历链表1加入map中，遍历链表2，判断是否map中存在，不存在加入map，存在返回当前节点

代码实现

import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;

        HashMap<ListNode,Integer> hashMap = new HashMap<ListNode,Integer>();
        while(current1!=null){
            hashMap.put(current1,null);
            current1 = current1.next;
        }
        while(current2!=null){
            if(hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        return null;
    }
}

复杂度

时间复杂度：0（n）空间复杂度：o(n)

yan0327 commented 2 years ago

思路：先遍历链表A，B得到各自的长度num1，num2. gap = abs（num1-num2）【abs为绝对值】如果num1大，则headA先移动gap步如果num2大，则headB先移动gap步然后两个链表同时移动，如果两个链表相等，则返回链表否则当一个链表走到尽头，for循环终止。返回nil

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil{
        return nil
    }
    num1,num2:=0,0
    cur1,cur2 := headA,headB
    for cur1 != nil{
        cur1 = cur1.Next
        num1++
    }
    for cur2 != nil{
        cur2 = cur2.Next
        num2++
    }
    gap := abs(num1-num2)
    if num1 > num2{
        for gap > 0{
            headA = headA.Next
            gap--
        }
    }else{
        for gap > 0{
            headB = headB.Next
            gap--
        }
    }
    for headA != nil&& headB != nil{
        if headA == headB{
            return headB
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}
func abs(x int) int{
    if x < 0{
        return -x
    }
        return x
}

时间复杂度O（n） n为两个链表长度的最大值空间复杂度O（1）

Alexno1no2 commented 2 years ago

题解：

将两个无环链表串起来，同时遍历，要么走到相交的节点，要么走到最后空节点

复杂度：

O(M+N)

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

xj-yan commented 2 years ago

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        curtA, curtB = headA, headB
        while curtA != curtB:
            curtA = curtA.next if curtA else headB
            curtB = curtB.next if curtB else headA
        return curtA

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

wxj783428795 commented 2 years ago

思路

先遍历A链表，将左右节点存储在set中在遍历B链表，如果节点在set中已存在，则当前节点就是相交起始节点

代码

var getIntersectionNode = function (headA, headB) {
    let set = new Set();
    while (headA) {
        set.add(headA);
        headA = headA.next;
    }
    while (headB) {
        if (set.has(headB)) return headB;
        headB = headB.next;
    }
    return null
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

时间复杂度：O(N) N为a或b的节点数
空间复杂度：O(N) N为a或b的节点数

CodeWithIris commented 2 years ago

Note (Hash Set)

Iterate over linked list A, storing the nodes in linked list A in the hash set.
Then iterate through the linked list B, and the first node it encounters that also exists in the hash set is the result returned. If the node is not found after iterating through linked list B, return nullptr.

Solution (C++)


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode* > hashset;
        ListNode* tmp = headA;
        while(tmp!=nullptr){
            hashset.insert(tmp);
            tmp = tmp->next;
        }
        tmp = headB;
        while(tmp!=nullptr){
            if(hashset.count(tmp)) return tmp;
            tmp = tmp->next;
        }
        return nullptr;
    }
};

Complexity

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

Grendelta commented 2 years ago

思路

使用双指针，分别遍历A和B，完成遍历后指针指向另一个链表的表头。当指针相交时便得到链表相交的节点。

代码

class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ a, b = headA, headB while a != b: if a: a = a.next else: a = headB if b: b = b.next else: b = headA return a

复杂度

时间复杂度 O(N)

空间复杂度 O(1)

q815101630 commented 2 years ago

思路

假设A链表单独的部分用A 表示， B链表单独的部分用B表示，共同拥有部分用C表示，因为 A+C+B = B+C+A；我们可以同时遍历两个链表并且让他们为None时跳到对方头节点, 直到两者都为空或相同，表示他们相交的节点位置或者不相交（一旦都为空一定不相交，如果A B 长度一样那么在到达C 入口时便会跳出while）

# 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:

            a = a.next
            b = b.next

            if not a and not b:
                return None

            if not a:
                a = headB

            if not b:
                b = headA

        return a

时间 O(m+n) ; m n 为各自链表长度空间 O(1)

charlestang commented 2 years ago

思路

双指针，把两个链表联成环遍历一遍后，如果有交点，比如会在交点遇到，如果没有交点比如会在最后的结尾遇到。因为两个链表各遍历一遍，正好走过的节点一样多。

代码

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

时间复杂度 O(n)

ozhfo commented 2 years ago

思路

太呆了只想到了栈的做法两个链表都倒过来然后依次取就找到相交的点了
不过白板一次过了还不错

代码

/**
 * 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;
        }
        Stack<ListNode> stackA = new Stack();
        ListNode preA = headA;
        while(preA != null){
            stackA.push(preA);
            preA = preA.next;
        }

        Stack<ListNode> stackB = new Stack();
        ListNode preB = headB;
        while(preB != null){
            stackB.push(preB);
            preB = preB.next;
        }
        // 然后一起出栈
        ListNode result = null;
        while(!stackA.isEmpty() && !stackB.isEmpty()){
            preA = stackA.pop();
            preB = stackB.pop();
            if(preA == preB){
                result = preA;
            }else{
                break;
            }
        }
        return result;
    }
}

复杂度

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

hulichao commented 2 years ago

思路

case 有三种 1 > 2， 1 < 2, 1 != 2 使用双指针，在第三种会都为null然后相对，另外两种会相交，假设A链表单独的部分用A 表示， B链表单独的部分用B表示，共同拥有部分用C表示，因为 A+C+B = B+C+A；我们可以同时遍历两个链表并且让他们为null时跳到对方头节点, 直到两者都为空或相同，表示他们相交的节点位置或者不相交（一旦都为空一定不相交，如果A B 长度一样那么在到达C 入口时便会跳出while）

代码

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

        return h1;

    }
}

复杂度分析

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

Yutong-Dai commented 2 years ago

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        curA = headA
        curB = headB
        if not headA or not headB:
            return None
        while curA != curB:
            if not curA:
                curA = headB
            else:
                curA = curA.next
            if not curB:
                curB = headA
            else:
                curB = curB.next
        return curA

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

zwmanman commented 2 years ago

思路

two pointers each starts from listA and listB
lenght(listA) + length(listB) = length(listB) + length(listA)
when there is intersection, the common node is where they met

代码


class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p1 = headA
        p2 = headB

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

            if not p2:
                p2 = headA
            else:
                p2 = p2.next
        return p1

复杂度分析

时间复杂度：O(N)，其中 N 为两个链表长度。
空间复杂度：O(1)

pengfeichencpf commented 2 years ago

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; int lenA = getLength(headA), lenB = getLength(headB); if (lenA > lenB) { for (int i = 0; i < lenA - lenB; ++i) headA = headA.next; } else { for (int i = 0; i < lenB - lenA; ++i) headB = headB.next; } while (headA != null && headB != null && headA != headB) { headA = headA.next; headB = headB.next; } return (headA != null && headB != null) ? headA : null; } public int getLength(ListNode head) { int cnt = 0; while (head != null) { ++cnt; head = head.next; } return cnt; } }

zhy3213 commented 2 years ago

思路

哈希

代码

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        s=set()
        while headA:
            s.add(headA)
            headA=headA.next
        while headB:
            if headB in s:
                break
            headB=headB.next
        if headB:
            return headB
        return None

CoreJa commented 2 years ago

思路

朴素思想，算长度差，对齐
链表互补法，A走完了从B继续走，B走完了从A继续走。两个指针都走了同样的长度
第三个方法同上，写法更简洁，看代码

代码

class Solution:
    # 朴素思想，算长度差，对齐
    def getIntersectionNode1(self, headA: ListNode, headB: ListNode) -> ListNode:
        start = ListNode(0)
        p = start
        p.next = headA
        cntA = 0
        while p := p.next:
            cntA += 1
        p = start
        p.next = headB
        cntB = 0
        while p := p.next:
            cntB += 1

        if cntA > cntB:
            cnt = cntA - cntB
            p, q = headA, headB
        else:
            cnt = cntB - cntA
            p, q = headB, headA

        while cnt:
            p = p.next
            cnt -= 1

        while p != q and (p := p.next) and (q := q.next):
            continue
        return p

    # 链表互补法，A走完了从B继续走，B走完了从A继续走。两个指针都走了同样的长度
    def getIntersectionNode2(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = ListNode(), ListNode()
        p.next, q.next = headA, headB
        headA, headB = p, q

        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

    # 同上，写法更简洁
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

Yachen-Guo commented 2 years ago

思路：通过A1+A2(B2)+B1 = B1 + B2(A2) + A1 的方式对齐两个链表，直到两个指针相等时停下，如果返回值不为空，则说明找到了交点，如果为空，则说明无交点并返回null

时间复杂度：O(N)

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

pangjiadai commented 2 years ago

Python 3

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 有交点在交点处走了同样的距离
        # 无交点走了A+B，在末尾处 a == b == None
        a = headA
        b = headB

        while a!=b:
            a = a.next if a else headB
            b = b.next if b else headA

        return a

yunomin commented 2 years ago

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:

        s = set()
        node = headA
        while node:
            s.add(node)
            node = node.next

        node = headB
        while node:
            if node in s: return node
            node = node.next

feifan-bai commented 2 years ago

思路

Curculate two points to the end
When p1 == p2, end the while loop

The end point is the intersection 代码

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

复杂度分析

时间复杂度：O(N), N = len(headA) + len(headB)
空间复杂度：O(1)

ZhangNN2018 commented 2 years ago

思路

a+c+b+c
b+c+a+c
让pa遍历完链表A之后开始遍历链表B，让pb遍历完链表B之后开始遍历链表A，这样两个指针同时到达相交点。

复杂度

时间复杂度: O(m+n), m和n分别是两个链表的长度；
空间复杂度: O(1)。

代码

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """  
        pa=headA
        pb=headB
        while pa != pb: 
            #如果pa指针走完了链表a，接着开始走b
            if pa:
                pa=pa.next
            else:
                pa=headB
            #如果pb走完了链表b,接着走b
            if pb:
                pb=pb.next
            else:
                pb=headA
        #走到两个链表相交的节点时，pa和pb走了相同的路程。
        return pa

yingliucreates commented 2 years ago

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

Tao-Mao commented 2 years ago

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 a = headA;
        ListNode 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;
    }
}

XinnXuu commented 2 years ago

思路

指针ptrA和指针ptrB分别遍历两条AB链表，设a为A链表的单独部分，b为B链表的单独部分，c为共有部分。因为 a+c+b = b+c+a，则若到链表尾则重定向到另一条链表的表头，若有相交点则两指针必然相遇。

代码

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

复杂度分析

时间复杂度：O(N)，N为总节点个数。
空间复杂度：O(1)

Bochengwan commented 2 years ago

思路

通过set存储一个list的全部节点，然后检查另外一个list的节点，直到找到第一个相同的。

代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node_set = set()

        while headA:
            node_set.add(headA)
            headA = headA.next
        while headB:
            if headB in node_set:

                return headB
            headB = headB.next
        return None

复杂度分析

时间复杂度：O(N+M)，其中 N 为数组长度。
空间复杂度：O(N)

Frederickfan commented 2 years ago

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pA = headA 
        pB = headB 

        while pA != None or pB != None:
            if pA == pB: 
                return pA 

            if pA == None: 
                pA = headB 
            else: 
                pA = pA.next 

            if pB == None: 
                pB = headA 
            else: 
                pB = pB.next 

        return None

freesan44 commented 2 years ago

思路

双指针交叉实现

关键点

代码

语言支持：Python3

Python3 Code:


# 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:
        ANode = headA
        BNode = headB
        ALink,BLink = False, False
        while ANode and BNode:
            # print(ANode.val,BNode.val)
            if ANode == BNode:
                return ANode

            ANode = ANode.next
            BNode = BNode.next
            if ANode == None and ALink != True:
                ANode = headB
                ALink = True
            if BNode == None and BLink != True:
                BNode = headA
                BLink = True
        # print("fail")
        return None

复杂度分析

令 n 为数组长度。

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

yuetong3yu commented 2 years ago

160. 相交链表

听说考察频率很高，比较简单，不作多说明。

哈希法

先遍历一遍链表 A，把走过的每个节点都存入一个额外的哈希中。然后再遍历链表 B，如果有哈希中已存在的节点则返回。

var getIntersectionNode = function (headA, headB) {
  // hash
  const hash = new Map()
  let p = headA
  while (p) {
    hash.set(p, 1)
    p = p.next
  }
  let p2 = headB
  while (p2) {
    if (hash.has(p2)) {
      return p2
    }
    p2 = p2.next
  }
  return null
}

时间复杂度：O(N); 空间复杂度：O(N); 这里的 N 取决于相交点的长度，但按照最坏空间算，就是 O(N)

双指针法

用两个指针，当 A 指针遍历到 A 链表的尾节点的时候，将它重置到 B 链表的头节点。同理，将 B 指针重置到 B 链表的头节点。

在第二次遍历的过程中，如果这个两个链表有相交点的话，则它们一定会相遇，否则不会。

var getIntersectionNode = function (headA, headB) {
  let p1 = headA
  let p2 = headB
  while (p1 != p2) {
    p1 = p1 ? p1.next : head
    p2 = p2 ? p2.next : head
  }
  return p1
}

Husky-Gong commented 2 years ago

Solution

If it gets to the tail of one list, then start from the other one
If no intersection between these 2 lists, A and B will get null, then break while loop

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 curA = headA, curB = headB;

        while (curA != curB) {
            curA = curA == null? headB : curA.next;
            curB = curB == null? headA : curB.next;
        }

        return curA;
    }
}

Complexity

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

tongxw commented 2 years ago

思路

双指针a和b一起遍历链表 a先指向headA，遍历结束后指向headB b先指向headB，遍历结束后指向headA 最后a == b的时候就是相交节点，或者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;
    }
}

TC: O(m + n)
SC: O(1)

hdyhdy commented 2 years ago

思路：哈希表，双指针（分别从两个链表进行遍历，遍历到头就转到另外一个链表，如果他们有相遇的可能性的话中途会相遇的，没有地方相遇最后都会指向nil）

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pa, pb := headA, headB
    for pa != pb{
        if pa == nil {
            pa = headB
        }else {
            pa = pa.Next
        }
        if pb == nil {
            pb = headA
        }else {
            pb = pb.Next
        }
    }
    return pa
}

时间复杂度（N）空间（1）

wangzehan123 commented 2 years ago


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

guoling0019 commented 2 years ago

思路

双指针

代码

语言支持：JavaScript

JavaScript Code:


/**
 * 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) {
    let nodeA=headA,nodeB=headB
    if(!nodeA||!nodeB){
        return null
    }
    while(nodeA!=nodeB){
        nodeA=nodeA?nodeA.next:headB
        nodeB=nodeB?nodeB.next:headA
    }
    return nodeA
};

复杂度分析

令 n 为数组长度。

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

falconruo commented 2 years ago

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

复杂度分析:

时间复杂度: 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;
    }
};

Davont commented 2 years ago

思路

暴力，我太菜了，不说了，看讲义去了

Code

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

1149004121 commented 2 years ago

160. 相交链表

思路

如果存在交点，指针A遍历完链表A再遍历链表B，指针B遍历完链表B再遍历链表A，两指针应该在交点处相遇；如果不存在交点，则两指针最后都指向null。

代码


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

复杂度分析

时间复杂度：O(N + M)，N为链表A长度，M为链表B长度。
空间复杂度：O(1)。

rootdavid commented 2 years ago

/**
 * 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* p1 = headA;
      ListNode* p2 = headB;

      while (p1 != p2) {
        if (p1 == NULL) p1 = headB;
        else p1 = p1->next;

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

      return p1;

    }
};

Myleswork commented 2 years ago

第十天（天气🌤）

思路一

将两链表起始遍历位置设为同一相对位置，这样往下遍历就一定能同时到达相交的节点，返回即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode *head){
        int length = 0;
        while(head){
            length++;
            head=head->next;
        }
        return length;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        int distract = abs(lengthA-lengthB);
        if(lengthA>lengthB){
            while(distract--){
                headA = headA->next;
            }
        }
        else{
            while(distract--){
                headB = headB->next;
            }
        }
        while(headA && headA!=headB){
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
};

复杂度分析

时间复杂度：O(max(lenA,lenB)) 计算链表长度产生的复杂度

空间复杂度：O(1)

思路二

设置双指针，分别首先各自遍历两链表，当其中任一指针遍历到链表尾，转而遍历另一链表，在遍历一个周期之后，两指针的相对位置会相同，在第二次遍历即可找到相交节点。

乍一看比较难理解，画一下就知道了，两个圈加起来的长度是相等的。

代码

/**
 * 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* key1 = headA;
        ListNode* key2 = headB;
        while(key1 != key2){
            key1 = key1 == NULL ? headB : key1->next;
            key2 = key2 == NULL ? headA : key2->next;
        }
        return key1;
    }
};

复杂度分析

时间复杂度：O(n+m) 两链表相加之后长度相同，所以才会同时到达第一个相交节点

空间复杂度：O(1)

suukii commented 2 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)$

haixiaolu commented 2 years ago

思路

讲义里的双指针思路

使用a, b两个指针分别指向A， B这两条链表的头，两个指针同时向后移动
当a到达链表的尾部时，重定位到链表B的头节点
当b到达链表的尾部时，重定位到链表A的头节点
a， b指针相遇的点位相交的起始点，否则没有相交点

代码 / Python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # two pointers

        a, b = headA, headB

        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

复杂度分析

Time: O(n + m). n, m are the length of the two Linked List
Space: O(1)

RocJeMaintiendrai commented 2 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) {
            if(a == null) {
                a = headB;
            } else {
                a = a.next;
            }
            if(b == null) {
                b = headA;
            } else {
                b = b.next;
            }
        }
        return a;
    }
}

复杂度分析

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

shamworld commented 2 years ago

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

732837590 commented 2 years ago

双指针遍历 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    ListNode A = headA , B = headB;

    while(A != B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }

    return A;
}

}

iambigchen commented 2 years ago

思路

两个链表相同速度向后移动，如果某一条到了尾端，继续移动一步，再下次移动时重新指向另外一条的顶部。两次遍历后，两遍的移动距离相同，都是A+B+1。如果两条链表有相交，则必然再中间某次会相遇。如果没有相交，则两次遍历结束后都同时指向了null

关键点

遍历到尾端，不立马指向另外一条链表的顶部，这样可以避免死循环和判断是否已经遍历过尾端。

代码

语言支持：JavaScript

JavaScript Code:


/**
 * 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) {
    let A = headA, B = headB
    while (A != B) {
        A = A == null ? headB : A.next
        B = B == null ? headA : B.next
    }
    return A 
};

复杂度分析

令 n 为数组长度。

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

思路2

遍历其中一条链表，并用哈希表存在改值。再遍历另外一条链表，判断哈希表中是否有该值

关键点

代码

语言支持：JavaScript

JavaScript Code:


/**
 * 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) {
    let map = new Set()
    while(headA != null) {
        map.add(headA)
        headA = headA.next
    }
    while(headB != null) {
        if (map.has(headB)) {
            return headB
        }
        headB = headB.next
    }
    return null
};

复杂度分析

令 n 为数组长度。

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

ZacheryCao commented 2 years ago

Idea:

Chasing poblem. Let's say linkedlist A length is l1 + l3, inkedlist B length is l2+l3, and the intersected linkedlist length is l3. We also have l2 = l1 + c. We first iterate though both linkedlist till one is at the end. Here, linkedlist A will finish first, which means, linkedlist B is c positions away from the end. We assign a pointer PB to the beginning of linkedlist B, and let linkedlist B finish the rest steps. Also keep moving PB at the same time. When linkedlist B is finished, PB has already moved c. Now, we assign another pointer PA to the beigning of linkedlist A. Currently, PA and PB are at the same steps away from the intersected point. We move PA and PB step by step till they meet. If one of them hits the tail first, which means there is not intersection. Otherwise, the intersected node will be the node they meet.

Code:

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        dummyA, dummyB, dummyC = headA, headB, None
        while dummyA and dummyB:
            dummyA= dummyA.next
            dummyB=dummyB.next
        if not dummyA:
            dummyC = dummyB
            dummyA = headB
            dummyB = headA
        else:
            dummyC = dummyA
            dummyA = headA
            dummyB = headB
        while dummyC:
            dummyA = dummyA.next
            dummyC = dummyC.next
        while dummyA and dummyB and dummyA!=dummyB:
            dummyA=dummyA.next
            dummyB=dummyB.next
        return dummyA if dummyA else None

Commplexity:

Time: Average: O(l1+l2+l3). l1, l3 is the length of the linkedlist not intersected part. l2 is the length of the intersected part. Time: Worst: O(m+n). There is not intersection, the worst case will be the length of linkedlist A + linkedlistB Space: O(1)

Yark-yao commented 2 years ago

思路

先遍历链表A，用map记录每个节点，再遍历链表B，若B的节点在map中，则说明是相交节点

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    // 先遍历一次链表A，用map存储每个节点是否被访问，
    // 再遍历链表B，如果该节点已经被访问过，则说明是相交节点
    const visitMap = new Map()
    while(headA){
        visitMap.set(headA,true)
        headA = headA.next
    }
    while(headB){
        if(visitMap.get(headB)){
            return headB
        }
        headB = headB.next
    }
    return null
};

复杂度

时间：O(M+N) 空间: O(M)

wenjialu commented 2 years ago

thought

循环条件：不相等 a + common + b = b + common + a
if come to end, go for another linkedlist, 退出循环：相等/ 都为None
if == .return ; if none, none.

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 
        #如果不相交，不管两条链表长度是否一致都会走到另一条链表上的终点。因为 a + b = b + a（见下面）
        # 26 4 1 5
        # 15 2 6 4

com

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

Flower-F commented 2 years ago

解题思路

如果指针 pA 不为空，则将指针 A 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。

代码

/**
 * 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) {
    let curA = headA, curB = headB;

    while (curA !== curB) {
        curA = curA ? curA.next : headB;
        curB = curB ? curB.next : headA;
    }

    return curA;
};

复杂度

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

ZJP1483469269 commented 2 years ago


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

zol013 commented 2 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 
        '''
        nodes_in_B = set()

        while headB != None:
            nodes_in_B.add(headB)
            headB = headB.next
        while headA != None:
            if headA in nodes_in_B:
                return headA
            headA = headA.next
        return None

        '''

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

【Day 10 】2021-12-21 - 160. 相交链表 #16

160. 相交链表

入选理由

题目地址

前置知识

题目描述

思路

代码实现

复杂度

题解：

复杂度：

思路

代码

复杂度分析

Note (Hash Set)

Solution (C++)

思路

代码

复杂度

思路

思路

代码

思路

代码

复杂度

思路

代码

思路

代码

思路

代码

思路

代码

Python 3

思路

复杂度

代码

Code

思路

代码

复杂度分析

思路

代码

思路

关键点

代码

哈希法

双指针法

Solution

Code

Complexity

思路

代码

思路

代码

思路

Code

160. 相交链表

思路

代码

第十天（天气🌤）

思路一

代码

思路二

代码

S1: 暴力法

S2: 哈希表

S3: 双指针

思路

代码 / Python

复杂度分析

代码

思路

关键点

代码

思路2

关键点

代码

Idea: