什么叫ARTS?
每周完成一个ARTS:
- Algorithm:每周至少做一个 leetcode 的算法题
- Review:阅读并点评至少一篇英文技术文章
- Tip:学习至少一个技术技巧
- Share:分享一篇有观点和思考的技术文章
作者:陈皓
链接:https://www.zhihu.com/question/301150832/answer/529809529
来源:知乎
Delete Node in a Linked List
从节点唯一的单链表中删除一个节点,不用返回任意数值。
1 | Input: head = [4,5,1,9], node = 5 |
方法一
- 将下一个节点的值复制到当前节点。注意node=node.next不会改变原链表。
- 删除下一个节点。
1 | /** |
Remove Nth Node From End of List
在一个循环内删掉链表的倒数第几个数。
1 | Given linked list: 1->2->3->4->5, and n = 2. |
方法一
- 先保存好头指针。
- 采用双指针进行遍历,第一个指针遍历到第n位后,第二个指针再从头开始遍历。
- 第一个指针到达末尾时,第二个指针的位置即是需要删除的位置,head就是头指针?
1 | /** |
单链表反转
使用递归和迭代两种方法实现。
1 | Input: 1->2->3->4->5->NULL |
方法一
- 迭代法:在首节点前插入头节点0,名字叫pre,另外cur节点指向head,不断的在pre后面插入cur->next,此时cur后移,直到cur为最后一个节点。
- 0->1->2->3->4->5->NULL origin
- 0->1->3->4->5->NULL 先把cur->next即2取出来,此时cur->next变成3
- 0->2->1->3->4->5->NULL 再把取出来的值即2插入到pre后面,注意插入的时候一定要以pre为基准
- 0->2->1->4->5->NULL 先把cur->next即3取出来,此时cur->next变成4
- 0->3->2->1->4->5->NULL 再把取出来的值即4插入到pre后面
1 | /** |
方法二
- 1->2->3->4->5->NULL
- 1->NULL 2->3->4->5->NULL
- 2->1->NULL 3->4->5->NULL
- 3->2->1->NULL 4->5->NULL
- 4->3->2->1->NULL 5->NULL
- 5->4->3->2->1->NULL
- 设置cur为NULL,先将head的next保存为next,将head插入cur头部,并更新cur。
- 更新head为next。
- 直到head为NULL。
1 | /** |
方法三
- 递归法。
- ⬇️1->2->3->4->5->NULL
- ⬇️1 head为1,head->next=2,⬆️5->4->3->2->1->NULL
- ⬇️2 head为2,head->next=3,⬆️5->4->3->2->NULL
- ⬇️3 head为3,head->next=4,⬆️5->4->3->NULL
- ⬇️4 head为4,head->next=5,⬆️5->4->NULL
- ⬇️5 head为5,head->next=NULL,⬆️递归开始返回,结果为head即5
- 先将问题递给最后的节点。最后的节点依次递回答案。
1 | /** |
Merge Two Sorted Lists
合并两个有序节点。
1 | Input: 1->2->4, 1->3->4 |
方法一
- 依次遍历两链表。
- 同时比较链表节点的大小,将节点大的插入到新链表中。(相等的情况就不需要考虑了,再比较一次就好了)
- 如果一方已经遍历完成,则将剩下的链表直接接入即可。
1 | /** |
方法二
- 递归法?如果是尾递归,答案不需要返回来,不容易堆栈溢出,如果再加一个行参作为答案栈即可使用。
- 1->2->4, 1->3->4
- 1 ⬇️ 2>-4, 1->3->4
- 1->1⬇️ 2->4, 3->4
- 1->1->2 ⬇️ 4, 3->4
- 1->1->2->3 ⬇️ 4, 4
- 1->1->2->3->4 ⬇️ 4
- 1->1->2->3->4->4
- 还需要向上递归找回头指针
1 | /** |
Palindrome Linked List
判断一个单链表是否为回文链表。
1 | Input: 1->2 |
方法一
- 使用快慢指针,先找到中间的节点。
- 再由中间的节点往两边做对比,需要提前做好数据备份,需要判断是奇偶数。
- 如果碰到不相等的,则返回false。
- 此时间复杂度为O(n)
1 | /** |
方法二
- 使用快慢指针,先找到中间的节点。
- 再由中间的节点往两边做对比,需要将后半段进行反转。
- 如果碰到不相等的,则返回false。
- 此时间复杂度为O(1)
1 | /** |
Linked List Cycle
判断链表中是否存在环。
1 | Input: head = [3,2,0,-4], pos = 1 |
方法一
- 采用快慢指针,判断指针是否会相遇,只能通过判断地址是否相等。
- 3,3
- 3 2,3 0
- 3 2 0,3 0 2
- 3 2 0 -4,3 0 2 -4
1 | /** |
方法二
- 使用hash set,不断查看之前的set中是否存在相同的节点了,如果存在,证明就是一个环。
1 | /** |