题目
给定两个单链表头 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
后记
看上去好象是很简单的问题，但找不到正确的解决办法？居然没有想到如果后边的交叠，前边的属于多余节点，裁掉多余节点就可以进行同时步进然后找到相同的节点了。
