2021-04-10：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函

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 mainimport "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代码
评论

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

你的鼓励让我更有动力

赞赏

0人进行了赞赏支持

你的鼓励让我更有动力

更多相关文章

随机推荐