Leetcode 每日一题 链表相关

[hankviv]

每日一题

[hankviv]

基本操作： 1、先设置上一个地址变量pre为空，当前地址为current传递过来的值 1、先把当前下一个地址保存起来。 temp := current.Next 2、当前地址的Next 指向上一个地址 current.Next = pre 3、pre,current = current,temp 整体前移一位，当前上一个指向当前，当前指向下一个

type ListNode struct {
    Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    current := head
    for nil != current{
        temp := current.Next
        current.Next = pre
        pre,current = current,temp
    }
    return pre
}

[hankviv]

递归操作 首先 一直递归到尾，然后在 出栈，head 依次是 倒数过来的节点。然后将head的下一个的next指向head，将head的next 指空，因为出栈会依次出来，所以不担心没有head的next

func reverseList3(head *ListNode) *ListNode{
    if head == nil || head.Next == nil{
        return head     
    }
    p := reverseList3(head)
    head.Next.Next = head
    head.Next = nil
    return p
}

[hankviv]

每日一题

[hankviv]

1、空间换时间 map法，遍历 如果有环的话就有重复的node，存储起来，看是否会重复就可以

func hasCycle(head *ListNode) bool {

    hashMap := make(map[*ListNode]int)
    for head != nil{
        if _,ok := hashMap[head];ok{
            return true
        }else{
            hashMap[head] = 1
        }
        head = head.Next
    }
    return false
}

[hankviv]

2、运动员赛跑模式 长指针和慢指针

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil{
        return false
    }
    var slow *ListNode
    var fast *ListNode
    for slow != fast{
        if fast == nil || fast.Next == nil{
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

把慢跑者视作参考系，这样来思考，慢跑者站着不动，快跑者速度为1，就会发现一定会相遇

[hankviv]

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

[hankviv]

解法一： 双指针法

func getKthFromEnd(head *ListNode, k int)  *ListNode {

    slow,fast := head,head
    t := 0

    for fast != nil{
        if t >= k{
            slow = slow.Next
        }
        fast = fast.Next
        t ++
    }
    return slow
}