2021-04-10：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null。【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
福大大 答案2021-04-10：
1.获取head1和head2的第一个入环节点。
2.head1和head2环节点的3种情况。
2.1.如果head1和head2只有其中一个有环，直接返回false。
2.2.如果head1和head2都没环。双指针，见力扣【剑指 Offer 52. 两个链表的第一个公共节点】。
2.3.如果head1和head2都有环。精髓在这里。
2.3.1.head1和head2根据入环节点分别断成两个链表。
2.3.2.head1左部分和head2左部分，根据2.2步骤求交点。保存在ans中。
2.3.3.head1和head2左右部分分别合并。
2.3.如果ans为空，需要循环判断head1的入环节点，如果循环了一圈都没找到head2中的入环节点，ans肯定为空；如果找到了，ans为head1的入环节点。
3.返回ans。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
head1 := &ListNode{Val: 1}
head1.Next = &ListNode{Val: 2}
head1.Next.Next = &ListNode{Val: 3}
head1.Next.Next.Next = &ListNode{Val: 4}
head1.Next.Next.Next.Next = &ListNode{Val: 5}
head1.Next.Next.Next.Next.Next = &ListNode{Val: 6}
head1.Next.Next.Next.Next.Next.Next = head1.Next.Next
head2 := &ListNode{Val: 7}
head2.Next = &ListNode{Val: 8}
head2.Next.Next = head1.Next.Next.Next.Next
ret := getIntersectionNode(head1, head2)
fmt.Println(ret)
}
//Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func getIntersectionNode(head1, head2 *ListNode) *ListNode {
if head1 == nil || head2 == nil {
return nil
}
loop1 := GetLoopNode(head1)
loop2 := GetLoopNode(head2)
if loop1 == nil && loop2 == nil {
return NoLoop(head1, head2)
}
if loop1 != nil && loop2 != nil {
return BothLoop(head1, loop1, head2, loop2)
}
return nil
}
//获取入环节点
func GetLoopNode(head *ListNode) *ListNode {
if head.Next == nil || head.Next.Next == nil {
return nil
}
slow := head.Next
fast := head.Next.Next
for slow != fast {
if fast.Next == nil || fast.Next.Next == nil {
return nil
}
fast = fast.Next.Next
slow = slow.Next
}
fast = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
//没有入环节点
func NoLoop(head1 *ListNode, head2 *ListNode) *ListNode {
cur1 := head1
cur2 := head2
for i := 0; i < 3; i++ {
for cur1 != nil && cur2 != nil {
if cur1 == cur2 {
return cur1
}
cur1 = cur1.Next
cur2 = cur2.Next
}
if cur1 == nil {
cur1 = head2
} else if cur2 == nil {
cur2 = head1
}
}
return nil
}
//有入环节点
func BothLoop(head1 *ListNode, loop1 *ListNode, head2 *ListNode, loop2 *ListNode) *ListNode {
loop1Next := loop1.Next
loop2Next := loop2.Next
//head1和head2根据入环节点分别断成两个链表。
loop1.Next = nil
loop2.Next = nil
//head1左部分和head2左部分，根据2.2步骤求交点。保存在ans中。
ans := NoLoop(head1, head2)
//head1和head2左右部分分别合并。
loop1.Next = loop1Next
loop2.Next = loop2Next
//如果ans为空，需要循环判断head1的入环节点，如果循环了一圈都没找到head2中的入环节点，ans肯定为空；如果找到了，ans为head1的入环节点。
if ans == nil {
loop1Copy := loop1.Next
for loop1Copy != loop1 {
if loop1Copy == loop2 {
ans = loop1
break
}
loop1Copy = loop1Copy.Next
}
}
//返回ans。
return ans
}
执行结果如下：
在这里插入图片描述
