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
}

执行结果如下：

---

左神java代码
评论