Intersection Of Two Linked Lists

题目描述

相交链表：

找到两个单链表相交的的起始节点。

解法

链表节点为：

type ListNode struct {
  Val int
  Next *ListNode
}

解法一：暴力

对于链表A的每个节点，在链表B中查找是否有重复节点。

解法二：哈希

遍历链表A的每个节点并且存储，然后遍历链表B，找到重复节点。

解法三：双指针

一个指针指向A，一个指针指向B，同时向前走。走到结尾再从另一个链表开始，直到相遇。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

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