说到算法这东西可以说是让很多程序员同学都痛不欲生的东西包括博主俗话说得好一杯茶一包烟一道算法写一天。但是以博主被leetcode反复折磨了千百遍后也算是总结了一些经验就用这篇博客与大家分享一下。我认为算法就是背加理解无他唯手熟尔记住一些基本的算法其实难题也就是基本算法的堆砌。本文主要以leetcode中的题单hot 100为例给大家分享主要使用go语言其他语言网上均有大量资料可供参考go语言相关相对较少。1、基本的需要记住的算法1.1相交列表这道题可以说是leetcode中最浪漫的题目了两个列表何时会相交呢就好比两个人何时会相遇呢只有你走过了他走的路他也走过了你走的路两个能相互体谅的人才最后能走到一起。这道题目也是一样假设链表A的头结点为temp_headA链表B的头结点为temp_haedB我们让两个节点同时开始移动(nodenode.next)让他们各自先走完自己的路即temp_headAnil或temp_headBnil,我们就让他们去走对方的路temp_headAheadB,temp_headBheadA,那么如果他们会相交的话就一定会出现temp_headAtemp_headB,而且相交点一定是相交链表的起点这个画个图就很明了了博主就不用数学给大家证明了,如果不相交的话则temp_headAnil且temp_headBnil。根据以上思路我们就能写出代码golangfunc getIntersectionNode(headA, headB *ListNode) *ListNode { temp_headA:headA temp_headB:headB for temp_headA!temp_headB{ if temp_headA!nil{ temp_headAtemp_headA.Next//走自己的路 }else{ temp_headAheadB//走对方的路 } if temp_headB!nil{ temp_headBtemp_headB.Next//走自己的路 }else{ temp_headBheadA//走对方的路 } } return temp_headA//如果相交temp_headA就是相交链表的头结点如果不相交temp_headAtemp_headBnil }1.2反转链表这道题可能开始会有点不友好了因为它会用到递归这让我想起了当年被递归折磨的场景了——一行一行代码调试就为看清递归过程呀。当然这道题也有非递归的写法这边两种方法都会讲解。怎么把一个链表反转呢很简单就是先找到原链表的尾节点在把链表从尾到头串起来不就行了原链表的尾节点就是反转链表的头结点。那么问题就是找和串的问题啦怎么能确定尾节点呢数组很好做就是arr[len(arr)-1]嘛可是注意哦这是链表条件应该是node.nextnil(尾结点的下一个节点肯定为空嘛)这样我们就找到了反转后的头结点。现在的问题就是穿起来这里可能会有点难理解我们举个例子node1-node2反着穿起来不就是应该是node1.next.nextnode1吗我们分开看node1.nextnode2题目条件哦node1-node2那么node1.next.nextnode1不就是node2.nextnode1那不就表示node2-node1这我们就完成的反转两个节点是这样其实更多的结点也是这样因为我们一次就处理当前节点和前一个节点嘛然后慢慢把原链表反转大问题拆成小问题来解决。以下是递归代码func reverseList(head *ListNode) *ListNode { if headnil||head.Nextnil{ return head } var frontreverseList(head.Next) head.Next.Nexthead head.Nextnil return front }其实代码还是很简单的只是递归对初学者没那么友好。其实递归少用才好毕竟比较消耗性能主要是装逼。以下为非递归代码func reverseList(head *ListNode) *ListNode { var pre *ListNode//存储前一个节点 cur:head for cur!nil{ next:cur.Next//先存储当前节点的下一个节点 cur.Nextpre//让当前节点的下一个节点指向前一个节点 precur//对于下一个循环当前节点就是前一个节点 curnext//让当前节点走向下一个节点 } return pre }在遍历链表时将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点因此必须事先存储其前一个节点。在更改引用之前还需要存储后一个节点。最后返回新的头引用。其实也不太好理解对吧慢慢沉淀吧。1.3环形链表如何证明一个链表存不存在环呢这就你好比你要如何证明学校操场是一个环形呢自己去跑一圈不就知道了但只靠你自己你还证明不了只缘身在此山中嘛你需要一个对照比如有一个你暗恋的女生她也在操场跑步你发现后雄性激素飙升立马加快速度超过她然后接着按照比她快的速度不停得跑那么如果操场是环形的话你一定会再遇见她如果不是的话你就永远也看不到她了对于链表我们只需要一个快慢指针快指针比慢指针跑得快一点只能是一点哦如果链表存在环形的话快慢指针一定会相遇。这个思路很简单我就不多说了。代码如下func hasCycle(head *ListNode) bool { if headnil||head.Nextnil{ return false } fast:head//快指针 slow:head//慢指针 for fast!nilfast.Next!nil{ fastfast.Next.Next slowslow.Next if fastslow{//相等说明相遇了链表存在环形 return true } } return false }1.4删除链表的倒数第N个节点要写这道题我们首先要知道如何删除链表中的节点我们来举个例子node1-node2-node3假设我们要删除node2这个节点那么我们只需要让node1.nextnode1.next.next就行了因为node1.next.nextnode3,所以就相当于node1.nextnode3,那么就相当于node1-node3,当然啦我们只是从逻辑层面把node2删除了在物理层面上它还是存在的。那么聪明的你已经发现了上面例子我们要删除的是node2,但实际上我们控制的是node1的逻辑也就是说删除倒数第二个节点实际上我们操作的是倒数第三个节点。那么也就是说删除倒数第N个节点我们就要找到倒数第N1个节点。那么这个思路就很简单了我们只需要让快指针比慢指针先多快走N步然后再让它们以相同的速度一起前进那么当快指针到达链表的尾结点时fast.nextnil,慢指针就到达了链表的倒数第N1个节点之后我们只需要像上面的操作一样删除倒数第N个节点就行了。代码如下func removeNthFromEnd(head *ListNode, n int) *ListNode { fast:head slow:head for n0{//让快指针先走N步 fastfast.Next n-- } if fastnil{//说明倒数第N个节点就是头结点 return head.Next } for fast.Next!nil{//找到fast为尾结点时慢指针的位置我们要操作慢指针 fastfast.Next slowslow.Next } slow.Nextslow.Next.Next return head }1.5.合并两个有序链表这道题就没什么说的了简单明了。我们分别比较两个链表的结点的值把较小的结点放入一个新的链表但要注意最后还要把剩下的没放进新链表的结点放进新链表哦。以下为代码实现func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { head:ListNode{}//新链表的头结点 dummy:head for list1!nillist2!nil{ if list1.Vallist2.Val{//把两个链表的较小值放入新链表 dummy.Nextlist1 dummydummy.Next list1list1.Next }else{ dummy.Nextlist2 dummydummy.Next list2list2.Next } } if list1!nil{ dummy.Nextlist1 } if list2!nil{ dummy.Nextlist2 } return head.Next//返回新链表的头结点 }2、稍微进阶一点的算法2.1回文链表这道题可以说是很经典了就是链表正着读跟反着读是一样的嘛比如1-2-2-1,那么聪明的你已经想到了这不就反转整个链表然后把翻转后的链表跟翻转前的链表逐一比对不就行了。确实可以这么写但你要注意把原链表保存一下哦不然翻转后的链表不知道该跟谁比。其实以上并不是最优解法因为我们还需要保存原链表能不能不保存呢再聪明一点我们把原链表看成两部分1-2,2-1我们只需要把后半部分反转然后把反转后的后半部分跟前半部分逐一比对就行了。那么问题就变成我们如何找到后半部分的起点思路很简单我们依旧定义快慢指针我们让快指针以慢指针两倍的速率前进那么当快指针走到尾结点时慢节点不就刚好走到了链表的一半吗那么代码如下func isPalindrome(head *ListNode) bool { if headnil||head.Nextnil{ return true } fast:head slow:head for fast!nilfast.Next!nil{//以两倍速度前进找到后半部分的头结点 fastfast.Next.Next slowslow.Next } var reverse func(*ListNode)*ListNode reversefunc(node *ListNode)*ListNode{ if node.Nextnil{ return node } tail:reverse(node.Next) node.Next.Nextnode node.Nextnil return tail } tail:reverse(slow)//反转后半部分 for tail!nilhead!nil{//反转后的部分与前一部分逐一比对 if tail.Valhead.Val{ tailtail.Next headhead.Next }else{ return false } } return true }2.2K个一组翻转链表每当写到leetcode困难题我才知道什么叫做任何困难都能打倒我如果看到这种题目第一次见就可以写出来那也可以说是天赋异禀了反正博主不是博主看到题目就睡着了只能一边刷一边忘啊最后总结出来规律忘得没那么慢刷得没那么快这道题的思路有些复杂大家可以参照博主的思路思考一下因为博主也没把握能写明白都是先射箭后画靶1.我们需要知道需要翻转多少次这个比较简单就是链表的长度除K嘛。2.反转链表与之前不同的是之前我们不知要反转多长的链表只知道要反转整个链表所以就一直找到node.nextnil为止,但现在我们知道了就是反转K个节点那么我就只需要node往下走一次K就减一当K1的时候node就是我们我们要反转的链表的尾节点了。3.就是这道题最难的地方了对细节的把控我们如何确定下一个翻转链表的头结点呢我们如何把一个个翻转后的链表串起来呢对于第一个问题我们之前在找到当前翻转链表的尾结点时我们会直接return node比如但现在我们需要再此之前在记录一下下一个要翻转节点的头节点假设我们设置一个全局变量dummy来记录吧那么就是如下代码if headnil||head.nextnil{ dummyhead.next return head }那么接下来我们要反转下一个链表就只需要把dummy传入就可以了。对于第二个问题两个链表怎么串起来其实关键在于前一个链表的尾结点和第二个链表头节点的关系前一个链表的尾结点不就是前一个链表翻转前的头结点吗那不就递归回溯到最后一个节点时的那个节点嘛不知道回溯的话可以去网上找视频看看这个博主很难讲清楚就是函数压栈出栈的过程第一轮递归放进去的是head所以回溯时最后出来的也是head我们也拿一个全局变量tail记录一下。其实到这里我们就可以写出完整的reverseN方法了大家可以先看一下。reverse(k int,node *ListNode)*ListNode{ if k1{ dummynode.next return node } pre:reverse(k-1,node.next) node.next.nextnode node.nextdummy tailnode return pre }现在前一个链表的尾节点我们也记录下来了我们只需要把尾结点连上当前翻转链表的头结点那不就是pre嘛当然中间还有一些细节博主就在代码里展示了你们细细品味完整代码如下var dummy *ListNodenil var tail *ListNodenil func reverseKGroup(head *ListNode, k int) *ListNode { var lengh0//记录链表的长度 temp:head for temp!nil{ temptemp.Next lengh } newhead:reverseN(k,head)//先把head和tail初始化一下再记录新链表的头结点 loop:lengh/k-1//要反转的操作次数-1是因为初始化的时候已经翻转了一次 for i:0;iloop;i{ head:dummy//当前翻转链表的头结点 temp_tail:tail//前一个翻转后链表的尾结点 temp_head:reverseN(k,head) temp_tail.Nexttemp_head } return newhead } func reverseN(n int,node *ListNode)*ListNode{ if n1{ dummynode.Next//记录下一个翻转链表的头结点 return node } pre:reverseN(n-1,node.Next) node.Next.Nextnode node.Nextdummy tailnode return pre }这种题目主要还是看自己的理解博主只能给出自己的理解。在哪跌倒就在哪站起来加油吧少年。2.3合并k个升序链表看到这道题是不是立马就联想到了合并两个有序链表这道题我们把k个链表两两组合在把组合后的链表和之后的链表组合不就可以了吗。思路也很简单主要是对操作熟练度的问题。代码如下func mergeKLists(lists []*ListNode) *ListNode { if len(lists) 0 { return nil } res : lists[0] for i : 1; i len(lists); i { res mergerTwoLists(res,lists[i]) } return res } func mergerTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { var head ListNode{Val: -1} var dummy head for list1 ! nil list2 ! nil { if list1.Val list2.Val { dummy.Next list1 list1 list1.Next dummy dummy.Next } else { dummy.Next list2 list2 list2.Next dummy dummy.Next } } if list1 ! nil { dummy.Next list1 } if list2 ! nil { dummy.Next list2 } return head.Next }这个解法比较好理解但时间复杂度较大达到了O(n*K),我们可以用分治法来降低时间复杂度func mergeKLists(lists []*ListNode) *ListNode { if len(lists)0{ return nil } for len(lists)1{ temp_list : []*ListNode{} for i:0;ilen(lists);i2{ var l1lists[i] var l2 *ListNodenil if i1len(lists){ l2lists[i1] } temp_listappend(temp_list,mergerTwoLists(l1,l2)) } liststemp_list } return lists[0] } func mergerTwoLists(list1 *ListNode,list2 *ListNode)*ListNode{ var headListNode{Val:-1} var dummyhead for list1!nillist2!nil{ if list1.Vallist2.Val{ dummy.Nextlist1 list1list1.Next dummydummy.Next }else{ dummy.Nextlist2 list2list2.Next dummydummy.Next } } if list1!nil{ dummy.Nextlist1 } if list2!nil{ dummy.Nextlist2 } return head.Next }3.一些比较考验手法的题3.1环形链表II这道题如果你能第一次写节写出来说明你要么是个数学家要么是个逻辑超强的编程小能手那么接下来博主要展现出自己超强的数学才能了。我们依旧设置快慢指针快指针的速度是慢指针的两倍起点到环入口的距离为s环的周长为m那么在相同的时间内快指针走过的路程Rfast会是慢指针走过路程Rslow的两倍即1Rfast2Rslow那么如果存在环的话在慢指针进入环后快指针一定会追上它而且一定会套圈我们假设快指针套了慢指针k圈也就是快指针比慢指针多走了k圈环的周长为m也就是多走了km的路程那么就得到2Rfast-Rslowkm结合12得到3Rslowkm因为我们要找入口嘛我们就找路口相关的关系我们注意到数学家惊人的注意力每当慢指针到达环的入口时都有4Rslowstmt为任意正整数那么我们观察34两式不难发现当快针追上慢指针时3式成立当慢指针到达入口时4式成立所以当快指针追上慢指针时慢指针还有s的距离到达入口那么接下来就是找s的过程s不就是起点到环入口的长度吗那么接下就很简单了我们让fast回到头结点slow不动再让两者一步步走当两者相遇fastslow时就是环的入口。完整代码如下func detectCycle(head *ListNode) *ListNode { if headnil||head.Nextnil{ return nil } var fasthead var slowhead for fast!nilfast.Next!nil{ fastfast.Next.Next slowslow.Next if fastslow{ fasthead//相遇后把fast放回头结点 for fast!slow{ fastfast.Next slowslow.Next } return slow//相遇时就是环的入口 } } return nil }3.2排序链表如这道题改为排序数组的话我相信大多数同学都能做出来这年代谁还不会写个冒牌排序了就算不会库函数总会调用把把数组扔进去不就行了。但是排序链表的话就比较难了但也可以借鉴排序数组的思路但不是冒泡而是借鉴快速排序和归并排序博主认为这两大排序才是最应该掌握的排序算法那么博主就用归并排序的思路给大家讲解不会归并的同学自己去网上学归并哈有点难度因为涉及到递归回溯是一个让人头痛的问题。归并排序的话博主认为主要有三个阶段拆开归并排序准确说归并的同时就在排序拆开对应递归的过程归并和排序对应回溯的过程。递归回溯的过程就不详细说了不是博主懒得打字是这个东西很难说清楚过程只能靠自己沉淀。完整代码如下func sortList(head *ListNode) *ListNode { if headnil||head.Nextnil{//拆到最小后退出递归 return head } slow,fast:head,head.Next for fast!nilfast.Next!nil{ fastfast.Next.Next slowslow.Next } temp:slow.Next//右链表的头结点 slow.Nextnil//切割左右链表 left:sortList(head) right:sortList(temp) //又是合并两个有序链表的模版 dummy:ListNode{} cur:dummy for left!nilright!nil{ if left.Valright.Val{ cur.Nextleft curcur.Next leftleft.Next }else{ cur.Nextright curcur.Next rightright.Next } } if left!nil{ cur.Nextleft } if right!nil{ cur.Nextright } return dummy.Next }注意这里我们开始让fasthead.next是因为我们要让慢指针处于中间靠左的位置不然有可能会发生无限递归。举个例子当链表长度为 2 时例如1 - 2初始slow指向1fast指向1进入循环slow移到2fast移到nil循环结束此时slow指向最后一个节点2temp slow.Next→nilslow.Next nil→ 将2的Next置空但左半部分仍为1 - 2因为1还指向2右半部分为nil然后递归sortList(head)又会处理同一个长度为 2 的链表无限递归。根本原因slow没有停在中间偏左的位置而是跑到了末尾导致左半部分没有真正被切断。3.3随机链表的复制这道题乍一看还挺吓人的可能有的的小伙伴第一次见就被它给吓到了主要是它给人一种写出来了但是好像我在原地转圈的感觉这道题最重要的一个点就是深拷贝理解了这个你才能知道这道题到底在干什么什么叫深拷贝就是修改原对象的值不会改变新的对象。举个例子假设我们有一个指针head *int1我们让tailhead,那么显然我们修改tail的值会影响head的值这叫浅拷贝。深拷贝就是p : new(int); *p *head这样修改p的值就不会影响head的值了因为我们已经为p分配了一个新的内存空间这道题的关键就是在这里。只是由于这里我们要记录一下每个节点的Random指针所以用hash表做个映射。完整代码如下func copyRandomList(head *Node) *Node { var hashmake(map[*Node]*Node) cur:head for cur!nil{ newNode:Node{Val:cur.Val}//深拷贝 hash[cur]newNode//把原节点和新节点都一一对应起来 curcur.Next } curhead for cur!nil{ hash[cur].Nexthash[cur.Next]//新链表的下一个节点就是原链表的下一个节点映射后的结点 hash[cur].Randomhash[cur.Random] curcur.Next } return hash[head] }3.4.两两交换链表中的节点有些小伙伴可能已经反应过来了这不就是之前的K个一组翻转链表让K2嘛没错确实可以这么写这里博主就是不掩饰了我们还是用常规写法做。var dummyListNode{ Val:-1, } dummy.Nexthead temp:dummy for temp.Next!niltemp.Next.Next!nil{ p:temp.Next q:temp.Next.Next temp.Nextq p.Nextq.Next q.Nextp tempp } return dummy.Next3.5LRU缓存这道题一定要多刷非常考验一个人的基本功底。其底层是一个双向的环形链表梦回B树的属于是只是B树的底层的链表不是环形好吧这个不重要。说实话没什么好讲得代码很简单主要是这种设计题的信息太少自己能不能构建出来type LRUCache struct { capacity int dummy *Node keyToNode map[int]*Node } type Node struct { prev *Node next *Node value int key int } func Constructor(capacity int) LRUCache { dummy : Node{} dummy.prev dummy dummy.next dummy return LRUCache{ capacity: capacity, dummy: dummy, keyToNode: make(map[int]*Node, capacity), } } func (this *LRUCache) Get(key int) int { node, ok : this.keyToNode[key] if !ok { return -1 } this.remove(node) this.pushFront(node) return node.value } func (this *LRUCache) Put(key int, value int) { node, ok : this.keyToNode[key] if ok { this.remove(node) this.pushFront(node) node.value value return } else { node : Node{ value: value, key: key, } this.pushFront(node) this.keyToNode[key] node } if len(this.keyToNode) this.capacity { backNode : this.dummy.prev this.remove(backNode) delete(this.keyToNode, backNode.key) } } func (this *LRUCache) remove(x *Node) { x.prev.next x.next x.next.prev x.prev } func (this *LRUCache) pushFront(x *Node) { head : this.dummy.next x.prev this.dummy this.dummy.next x x.next head head.prev x }OK链表相关的算法就分享到这里如果有不对的地方也欢迎大家留言指正。