题目

给定两个单链表头 headA headB。返回两个链表相交的节点，如果两个链表不相交，返回 null。

解析

假设两个链表相交，那么当 A 遍历到相交节点的时候，如何判断这个节点是否在 B 上？
假设有两条路在某一处之后是完全相交的，那么从这条路两端相向而行，一定能相遇。
所以，对于这个问题，首先从 A 节点开始，将 A 链表反向。得到 A 的末尾 tailA。
然后从 headB 和 tailA 相向而行，如果相遇，则相遇节点就是交集，如果不相遇，则没有交集返回空。
题目要求链表最终应该还原，那么可以在 tailA 反向的同时进行链表反向操作。

伪代码

for cur != nil
  cur.next = last
  cur = cur.next
  last = cur
tailA = last

for headB != nil && tailA != nil
  if headB == tailA || headB.next == tailA || tailA.next == headB  
    find = ?
  tailA.next = last
  last = tailA
  tailA = tailA.next

错误

以上代码逻辑并不能找到相交节点，因为在反向同步递进的过程中可能错过。

思路2

如果要让两个链表同时步进相遇，需要两个链表长度相同。
那么我们只需要让长一点的链表先走几布，让两个链表一样长。然后再同时步进即可。

伪代码

a = len(A)
b = len(B)

v = a-b
if v > 0
  A = A-> |v|
if v<0
  B = A->|v|
for A != nil && B != nil 
  if A == B
    return A
  A=A.next
  B=B.next
return nil

代码

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    na := headA
    nb := headB
    la := lenoflist(headA)
    lb := lenoflist(headB)
    
    v := la - lb
    if v > 0 {
        for i:=0; i < v; i++ {
            na = na.Next
        }
    }
    if v < 0 {
        for i:=v; i<0; i++ {
            nb = nb.Next
        }
    }
    for na != nil {
        if na == nb {
            break
        }
        na=na.Next
        nb=nb.Next
    }
    return na
}

func lenoflist(head *ListNode) int {
    rst := 0
    for head != nil {
        rst++
        head=head.Next
    }
    return rst
}

image.png

后记

看上去好象是很简单的问题，但找不到正确的解决办法？居然没有想到如果后边的交叠，前边的属于多余节点，裁掉多余节点就可以进行同时步进然后找到相同的节点了。