LeetCode力扣Golang实现/链表：21、83、141、142、160、206、234

包： container/list"

遍历：

for e := l.Front(); e != nil; e = e.Next() {
	// do something with e.Value
}

指针移动： p = p.Next

21、合并两个有序链表

递归相较于指针解法更节省空间，因为涉及出栈和入栈的操作

刚开始没有引入head结点，直接在list1、list2上操作，他会报错

:cannot use assignment (list1.Next) = (mergeTwoLists(list1.Next, l2)) as value (solution.go) 控制台

func mergeTwoLists(list1 *ListNode, listt2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	var head *ListNode
	if list1.Val > list2.Val {
		head = list2
		head.Next = mergeTwoLists(list1, list2.Next)
	} else {
		head = list1
		head.Next = mergeTwoLists(list1.Next, list2)
	}
	return head

}

83、删除排序链表中重复元素

我好像有一点悟到再设置一个结点的作用了，用来移动，正好可以直接输出值，所以就不用一个单单指针了，

func deleteDuplicates(head *ListNode) *ListNode {
        if head == nil {return head}
        crr := head
        for crr.Next !=nil {
            if crr.Val == crr.Next.Val{
                crr.Next =crr.Next.Next
            }else {
                crr = crr.Next
            }
        }
    
    return head

}

141、环形链表一

刚开始想到了哈希表，执行如下图，后来看了看发现是有数值重复但地址不同的元素，然后愚蠢了一把，想借用i存储下标，判断是否是同一个元素，但是一直报超出时间范围，

对啊我去，为什么不直接用记录结点啊

//4 ：如果下一个或者下下个为空，则一定无环

但是进入哈希表的时候存储结构体要{}{}

func hasCycle(head *ListNode) bool {
    if head == nil {return false }
    tmp :=make(map[*ListNode]struct{},0)
    for head.Next !=nil && head.Next.Next!=nil{
        _,ok :=  tmp[head] 
        if ok {
            return true
        }else{
            tmp[head] = struct{}{}
            head = head.Next
        }
    }
    return false
    
}

心情舒畅了

后来看了一下进阶要求，要实现空间O（1）等我研究一下

环形链表通用解法：弗洛伊德解法：快慢指针

化为追击问题，如果能追上，肯定有环！

又是这里，真的呵了，报错无效地址

panic: runtime error: invalid memory address or nil pointer dereference [signal SIGSEGV:

循环条件错了，head固定跟他就没关系了，这里忘记改了

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

142.环形链表二


func detectCycle(head *ListNode) *ListNode {
    fast,slow :=head,head
    var ans bool
    for fast !=nil && slow !=nil && fast.Next !=nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow{
            ans =  true
            break
        }
    }
    if ans{
        slow = head
        for  slow != fast{
            slow = slow.Next
            fast = fast.Next
        }
        return slow
    }
    return nil
}

160、相交链表

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA ==nil || headB == nil{
        return nil
    }
    pA,pB := headA,headB
    for pA!= pB {
        if pA != nil{
            pA = pA.Next
        }else{
            pA =headB
        }

        if pB != nil{
            pB = pB.Next
        }else{
            pB =headA
        }
    }
    return pA
}

206、反转链表

最后返回的刚开始写的now，所以结果一直为空，但是在出循环的时候now已经=nil 了，真正的新表头是pre

func reverseList(head *ListNode) *ListNode {
    now:= head
    var pre *ListNode
    for now != nil{
        next := now.Next
        now.Next =pre
        pre=now
        now =next
    }
    return pre
}

234、回文链表

在最后for 比较是比较的是值 Val，刚开始直接用结点，所有一直得到返结果


func isPalindrome(head *ListNode) bool {
    if head == nil{return true}
    fast,slow := head,head
    for fast !=nil && fast.Next !=nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    if fast !=nil { //为奇数个
    slow = slow.Next
    }

    slow = reverseList(slow)
    fast = head
    
    for slow !=nil {
        if slow.Val != fast.Val{
            return false
        }
        slow = slow.Next
        fast = fast.Next
    }
    return true
}
//反转链表
    func reverseList(head *ListNode) *ListNode {
    now:= head
    var pre *ListNode
    for now != nil{
        next := now.Next
        now.Next =pre
        pre=now
        now =next
    }
    return pre
}

876、链表的中间结点

上题用过了

func middleNode(head *ListNode) *ListNode {
    if head == nil{return nil}
    if head !=nil  && head.Next == nil{return head}
    fast,slow := head,head
    for fast !=nil && fast.Next !=nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow 
}

剑指offer22、返回链表中倒数第k个结点

大胆推测凡是要通过遍历确定长度进而确定位置的都可以用快慢指针

快指针先行k-1个

LeetCode力扣Golang实现/链表 ：21、83、141、142、160、206、234