剑指offer刷题 - day03

JZ23 链表中环的入口结点

我的思路

遍历节点，根据题意节点值范围在 1<=n<=10000 ，将遍历过的节点节点值取反，然后在循环过程中判断节点值是否为负，为负重新取正然后返回该节点。

package main

/*
type ListNode struct {
    Val  int
    Next *ListNode
}
*/

func EntryNodeOfLoop(pHead *ListNode) *ListNode {
    p := pHead
    for p != nil {
        if p.Val < 1 {
            p.Val *= -1
            return p
        }
        p.Val *= -1
        p = p.Next
    }
    return nil
}

官方思路 - 快慢双指针

快指针走两步，慢指针走一步，在有环的情况下，两个指针一定会相遇，如果没有环，快指针先一步指向 nil ，直接退出循环即可。

假设头节点到环的入口节点距离为 X，慢指针走过的距离为 X+Y

那么快指针走过的距离就为 2*(X+Y)，快指针比慢指针多走了一圈，园的长度就为 X+Y

画出示意图，可以推导出，相遇节点出发与从头节点一起出发，将会在环的入口节点相遇。

package main

/*
type ListNode struct {
    Val  int
    Next *ListNode
}
*/

func EntryNodeOfLoop(pHead *ListNode) *ListNode {
    fast, slow := pHead, pHead
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }

    slow = pHead
    for fast != slow {
        slow = slow.Next
        fast = fast.Next
    }
    return fast
}

JZ22 链表中倒数最后k个结点

我的思路

执行两次循环，一次取长度，一次获取指定指针

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
*/
func FindKthToTail(pHead *ListNode, k int) *ListNode {
    p := pHead
    len := 0
    for p != nil {
        len++
        p = p.Next
    }
    if k > len {
        return nil
    }
    i := 0
    p = pHead
    for i != len-k {
        i++
        p = p.Next
    }
    return p
}

官方思路 - 快慢双指针

让快指针先移动 k 步，两个指针距离是 k，然后再然后一起移动，当快指针到达终点，此时慢所在位置就是倒数 k 个位置

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
*/
func FindKthToTail(pHead *ListNode, k int) *ListNode {
    fast, slow := pHead, pHead
    i := 0
    for i < k && fast != nil {
        i++
        fast = fast.Next
    }
    if i != k {
        return nil
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}