0160._intersection_of_two_linked_lists.md

Navigation

• Navigation
• Links:
• Solution 1 哈希表（字典）
• Solution 2 双指针

Links:

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

Solution 1 哈希表（字典）

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

class Solution:
    """
        时间复杂度：O(m+n) = O(max(m, n))
        空间复杂度：O(m)或者O(n)
    """
    def getIntersectionNode(self, headA, headB):
        hashA  = {}
        while headA:
            hashA[headA] = 1    # 注意headA是引用，是地址，这就把示例1说通了。示例1中的两个1,节点的地址不同。
            headA = headA.next
        while headB:
            if hashA.get(headB):
                return headB
            headB = headB.next

---

Go

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	m := make(map[*ListNode]struct{})

	for headA != nil {
		m[headA] = struct{}{}
		headA = headA.Next
	}

	for headB != nil {
		if _, ok := m[headB]; ok {
			return headB
		}
		headB = headB.Next
	}

	return nil
}

Solution 2 双指针

两指针速度一样。 一个指针先跑完短链表，再跑长链表，停下在点a。 另一个指针先跑完长链表，再跑短链表，停下在点b。 如果a == b， 则说明有交点。（可以看示例的图去想）

class Solution:
    """
        时间复杂度：O(m+n) = O(max(m, n))
        空间复杂度：O(1)
    """
    def getIntersectionNode(self, headA, headB):
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

---

Go

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
}