春节7天练 Day 1：数组和链表

你好，我是王争。首先祝你新年快乐！

专栏的正文部分已经结束，相信这半年的时间，你学到了很多，究竟学习成果怎样呢？

我整理了数据结构和算法中必知必会的30个代码实现，从今天开始，分7天发布出来，供你复习巩固所用。你可以每天花一点时间，来完成测验。测验完成后，你可以根据结果，回到相应章节，有针对性地进行复习。

除此之外，@Smallfly 同学还整理了一份配套的LeetCode练习题，你也可以一起练习一下。在此，我谨代表我本人对@Smallfly 表示感谢！

另外，我还为假期坚持学习的同学准备了丰厚的春节加油礼包。

2月5日-2月14日，只要在专栏文章下的留言区写下你的答案，参与答题，并且留言被精选，即可获得极客时间10元无门槛优惠券。
7篇中的所有题目，只要回答正确3道及以上，即可获得极客时间99元专栏通用阅码。
如果7天连续参与答题，并且每天的留言均被精选，还可额外获得极客时间价值365元的每日一课年度会员。

关于数组和链表的几个必知必会的代码实现

数组

实现一个支持动态扩容的数组
实现一个大小固定的有序数组，支持动态增删改操作
实现两个有序数组合并为一个有序数组

链表

实现单链表、循环链表、双向链表，支持增删操作
实现单链表反转
实现两个有序的链表合并为一个有序链表
实现求链表的中间结点

对应的LeetCode练习题（@Smallfly 整理）

数组

Three Sum（求三数之和）

英文版：https://leetcode.com/problems/3sum/

中文版：https://leetcode-cn.com/problems/3sum/

Majority Element（求众数）

英文版：https://leetcode.com/problems/majority-element/

中文版：https://leetcode-cn.com/problems/majority-element/

Missing Positive（求缺失的第一个正数）

英文版：https://leetcode.com/problems/first-missing-positive/

中文版：https://leetcode-cn.com/problems/first-missing-positive/

链表

Linked List Cycle I（环形链表）

英文版：https://leetcode.com/problems/linked-list-cycle/

中文版：https://leetcode-cn.com/problems/linked-list-cycle/

Merge k Sorted Lists（合并k个排序链表）

英文版：https://leetcode.com/problems/merge-k-sorted-lists/

中文版：https://leetcode-cn.com/problems/merge-k-sorted-lists/

做完题目之后，你可以点击“请朋友读”，把测试题分享给你的朋友，说不定就帮他解决了一个难题。

祝你取得好成绩！明天见！

精选留言（15）

William 👍（4） 💬（1）
特地新开了一个git仓库，https://github.com/Si3ver/LeetCode。刷完5道题，思路大致写一下。1.数组三数之和，时间复杂度是O(n^2)，先排序，外层i遍历数组，内层左右双指针，寻找两数之和 = -nums[i]。 2. 求数组中出现次数大于一半的数字。复杂度O(n)，是利用摩尔投票法。3.求缺失的最小正整数，复杂度O(n)，思路是哈希表统计。4.环形链表用快慢指针。5.合并k个有序链表，用的是两两归并，据说用堆会更快，这个有待补充。
2019-02-06

峰 👍（4） 💬（1）
第三题，看这题，我就会想到用快排的思想在一堆数中求第n大。于是乎我就套，先把负数全部移掉，o(n)不影响。然后每轮迭代随机取个数n，比它小的放左边，比他大的放右边。比如说第一轮迭代，左边的数据个数小于n-1那么必然在左边。但这里有个问题是数据是可以重复的，怎么办，想呀想，我就选定n后，开始扫描，如果是1我就放第一个位置，如果是2我就放第二个位置，如果再有1，发现重复了，不用移动了，这样我就能计算小于n大于n的正整数有多少种了，然后就能迭代下去了。当然里面还有些细节，比如如果n很大已超过了数组长度，那说明那个数一定在左边。
2019-02-05

Ben 👍（2） 💬（1）
class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] 通过hash结构缓存去重值及出现的次数将值按正负区分, 将正负列表中的数字求和, 判断和的相反数是否仍存在于字典中 """ #将输入列表的值作为索引, 对应出现的次数作为新的字典结构的值 dic = {} for ele in nums: if ele not in dic: dic[ele] = 0 dic[ele] += 1 # 存在3个0的特殊情况 if 0 in dic and dic[0] > 2: rst = [[0, 0, 0]] else: rst = [] pos = [p for p in dic if p > 0] neg = [n for n in dic if n < 0] # 若全为正或负值, 不存在和为0的情况 for p in pos: for n in neg: inverse = -(p + n) if inverse in dic: if inverse == p and dic[p] > 1: rst.append([n, p, p]) elif inverse == n and dic[n] > 1: rst.append([n, n, p]) # 去重: 小于负值且大于正值可以排除掉重复使用二者之间的值 elif inverse < n or inverse > p or inverse == 0: rst.append([n, inverse, p]) return rst def majorityElement(self, nums): """ :type nums: List[int] :rtype: int hash反存值和出现的次数 """ #利用字典表反存值:出现的次数 dic = {} for i in nums: if i not in dic: dic[i] = 1 else: dic[i] +=1 #根据列表获取值最大的索引 vs = list(dic.values()) return list(dic.keys())[vs.index(max(vs))] def firstMissingPositiveFast(self, nums): """ :type nums: List[int] :rtype: int """ n = 1 while n in nums: n +=1 return n
2019-02-14

acqierement 👍（2） 💬（1）
自己总结了链表的部分算法，链表算是很简单的数据结构了，只要你心里有一个个节点的概念，必要时画图看一下还是很简单的。 1.单链表反转反转比较简单,就是要有一个先前节点prev和当前节点cur，要有一个临时节点保存cur的下一个节点（cur.next），否则反转之后你就找不到下一个节点了。然后让head指向前一个节点prev。之后继续移动cur和prev节点进行下一次反转 public ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null) { ListNode temp = cur.next; cur.next = prev; prev = cur; cur = temp; } return prev; } 2.两个有序的链表合并思路就是自己创建一个链表，每次从两个链表头中找到较小的那个节点，接到自己的那个链表中。说着很简单，但还是有很多细节要注意。 public ListNode mergeTwoLists(ListNode l1,ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = new ListNode(0); ListNode cur = head; while(l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; }else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 == null) cur.next = l2; if (l2 == null) cur.next = l1; return head.next; } 3.求链表的中间结点(如果是偶数，返回中间两个中靠右的那个）这个问题就很简单了，环的检测也可以用到这种方法。就是用快慢指针，快的前进两步，慢的前进一步，等到快的指针到结尾时，慢的指针就到了中点。 public ListNode findCenter(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }
2019-02-05

赵菁垚 👍（1） 💬（1）
王老师，请教您一个问题，想参加NOIP c++考这些算法吗？
2019-08-08

神盾局闹别扭 👍（1） 💬（1）
加油礼包的福利在哪里领呢？
2019-02-18

Neo_Zhang 👍（1） 💬（1）
Three Sum（求三数之和）Go语言： func threeSum(nums []int) [][]int { results := [][]int{} n := len(nums) if n == 0 || n < 3 { return results } sort.Ints(nums) //首先，对数组进行排序 for i := 0; i < n-2; i++ { if i > 0 && nums[i] == nums[i-1] { //如果相邻两个数相等 continue } target := -nums[i] left := i + 1 right := n - 1 for left < right { sum := nums[left] + nums[right] if sum == target { results = append(results, []int{nums[left], nums[right], nums[i]}) left++ right-- for left < right && nums[left] == nums[left-1] { left++ } for left < right && nums[right] == nums[right+1] { right-- } } else if sum > target { right-- } else if sum < target { left++ } } } return results }
2019-02-12

欢乐小熊 👍（1） 💬（1）
链表篇 1. 翻转单链表 /*翻转单链表*/ void reversalList(Node<int>* head) { Node<int>* p = head; Node<int>* prev = NULL; Node<int>* temp = NULL; while (p) { // 1. 保存要遍历的下一个结点 temp = p->next; // 2. 将 node->next 指向前驱结点 p->next = prev; // 3. 更新前驱结点 prev = p; // 4. 更新下一个要遍历的结点 p = temp; } } 2. 将两个有序的单链表合并 /* 合并两个有序链表, 将 list2 合并到 list1 中 */ Node<int>* mergeOrderList(Node<int>* list1, Node<int>* list2) { // 记录 list2 的头结点 Node<int>* head = list2; // 创建哨兵, 用于处理将 list2 中的元素插入到 list1 头结点前面的情况 Node<int>* sentry = new Node<int>(-1); sentry->next = list1; // 记录 list1 要遍历的元素 Node<int>* node = sentry; Node<int>* temp = NULL; while (node->next && head) { if (node->next->data > head->data) { temp = head->next; head->next = node->next; node->next = head; head = temp; } else { node = node->next; } } // 若 list2 的头结点不为 NULL, 则说明 list1 中的元素提前遍历结束了 // 剩下的 list2 中的元素均比 list1 中的大 // 直接将 list1 的尾结点连接到 list2 的首结点即可 if (head) { node->next = head; } // 释放哨兵结点内存 list1 = sentry->next; sentry->next = NULL; delete(sentry); return list1; } 3. 求单链表的中间结点 /* 查询单链表的中间结点 */ template<typename E> Node<E>* findMidNode(Node<E>* head, Node<E>** mid_node) { if (!head) { return NULL; } Node<E>* fast = head; Node<E>* slow = head; while (fast && fast->next && fast->next->next) { // 快指针走两步 fast = fast->next->next; // 慢指针走一步 slow = slow->next; } *mid_node = slow; }
2019-02-12

ALAN 👍（1） 💬（1）
array answer: import java.util.Arrays; public class Array1 { public int n; public int cur; public static int ary[]; //dynamic expand public static int fix[]; //fixed array public Array1(int size) { n=size; ary=new int [n]; } //dynamic expand public void insert(int ele) { if(cur==ary.length) { ary=Arrays.copyOf(ary, ary.length*2); System.out.println("length:"+ary.length); } ary[cur]=ele; cur++; } //fixed array --add public void add(int ele) { if(cur==fix.length) { return; } fix[cur]=ele; cur++; } //fixed array --delete public void delete() { if(cur==-1) return ; fix[cur]=0; cur--; } //fixed array --update public void update(int index,int ele) { if(index>=0 && index<fix.length) fix[index]=ele; } //merge public int[] merge(int[] a,int[] b ) { int[]c =new int[a.length+b.length]; int j=0,k=0; for(int i=0;i<a.length+b.length;i++) { if(j==a.length) { c[i]=b[k]; k++; continue; }else if(k==b.length){ c[i]=a[j]; j++; continue; } if(a[j]<b[k]) { c[i]=a[j]; j++; }else { c[i]=b[k]; k++; } } return c; } }
2019-02-07

陈小白( ´･ᴗ･` ) 👍（0） 💬（1）
这些题，我都做了一遍，除了那个“求缺失的第一个正数“没有相处方法，其它的都是自己做出来了。尤其最后那个”合并 k 个排序链表“，其实以前我也看过一次，当时的想法觉得是一个个取出来，然后排序然后再遍历。学完这堂课之后，看完题目，咦，这不是合并两个链表么？哦，合并多个，怎么处理多个问题？好像可以分治归并，嗯，好像是可以。我了个去，就有那种顿塞的感觉，那种开心。谢谢这门课。也谢谢老师，虽然课程里面还有很多没有明白，不过有些数据结构，算法，细细品味，好爽。
2019-10-06

coldpark 👍（0） 💬（1）
缺失的第一个正数那个题，如果让用额外内存空间还行，如果严格按照题意就是一道智力题，请问这种题在面时中遇到的多吗？
2019-10-05

二哥不再迷茫 👍（0） 💬（1）
Missing Positive；循环n次和2n次，时间复杂度都算是O(n)吧，空间复杂度也是如此! 根据他们的思路变通来的，不知道对不对，请老师帮忙看看，哈哈哈，现在老师是不是都不维护了。 public static int getFirstMissingPositive(int[] nums){ int result = 1; int[] arr = new int[nums.length+1]; for(int i =0;i<nums.length;i++){ if(nums[i] < arr.length && nums[i] > 0){ arr[nums[i]] = nums[i]; } } for(int j=1;j<arr.length;j++){ if(arr[j] == j){ result = j+1; }else { result = j; break; } } return result; }
2019-04-10

hopeful 👍（0） 💬（1）
//支持动态扩容的数组 public class MyArray { Object[] object ; private int capacity; private int count; MyArray(int capacity){ this.capacity = capacity; this.object = new Object[capacity]; this.count = 0; } public Object get(int i) { if(i<0 || i>=count) { return null; }else { return object[i]; } } public int size() { return this.count; } public int capacity() { return this.capacity; } public void add(int j, Object o) { if((count+1)>=capacity) { Object[] ob = new Object[2*capacity]; System.arraycopy(object, 0, ob, 0, count); this.object = ob; this.capacity = object.length; } if(j < 0 || j > count) { System.out.println("位置不合法"); return false; } for (int i = count; i > j; i--) { object[i] = object[i-1]; } object[j] = o; count++; return true; } public void addFirst(Object o) { if((count+1)>=capacity) { Object[] ob = new Object[2*capacity]; System.arraycopy(object, 0, ob, 0, count); this.object = ob; this.capacity = object.length; } for (int i = count; i > 0; i--) { object[i] = object[i-1]; } object[0] = o; count++; } public void addLast(Object o) { if((count+1)>=capacity) { Object[] ob = new Object[2*capacity]; System.arraycopy(object, 0, ob, 0, count); this.object = ob; this.capacity = object.length; } object[this.size()] = o; count++; } public boolean delete(int index) { if(index < 0 || index >= count) return false; for (int i = index + 1; i < count; i++) { object[i-1] = object[i]; } count--; return true; } public Object[] list() { Object[] o = new Object[this.size()]; for (int i = 0; i < o.length; i++) { o[i] = object[i]; } return o; } }
2019-02-13

xumc 👍（0） 💬（1）
数组基础 - 有序数组（2） func (array *OrderArray) Remove(val int) { index := array.Find(val) if index == -1 { return } for i := index; i < len(*array)-1; i++ { (*array)[i] = (*array)[i+1] } //清除最后一个节点 (*array) = (*array)[0 : len(*array)-1] } //a := OrderArray{9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12} //a.RemoveAll(9) func (array *OrderArray) RemoveAll(val int) { indexs := array.FindAll(val) if len(indexs) == 0 { return } sort.Ints(indexs) start := indexs[0] leng := len(indexs) for i := start; i+leng < len(*array); i++ { (*array)[i] = (*array)[i+leng] } //清除最后n节点 (*array) = (*array)[0 : len(*array)-leng] } func (array *OrderArray) Set(index int, val int) { leng := len(*array) if index > leng || index < 0 || leng == 0 { panic("cannot set") } if (leng == 1 && index == 0) || (index == 0) && val <= (*array)[1] || (index == leng-1 && val >= (*array)[leng-2]) { (*array)[index] = val return } if val > (*array)[index+1] || val < (*array)[index-1] { panic("cannot set") } (*array)[index] = val } 基础薄弱，其他我慢慢写，谢谢老师。
2019-02-13

未来的胡先森 👍（0） 💬（1）
「三数之和」解题思路： 1、先将一维数组升序排序，第 1 、2、3 三个数也按照升序选取，但出现符合题目要求的组合出现则加入要返回的二维数组中。 2、在新的组合出现时判断是否与前一个组合相同，若是则放弃该组合。 3、初始化申请二维数组大小为 64 若不够则扩充 2 倍大小。 4、优化代码，防止超时。第 1 个数为正数时即可结束循环，将三重循环优化成双重循环。代码 int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int** threeSum(int* nums, int numsSize, int* returnSize) { qsort(nums, numsSize, sizeof(int), compare); int flag = numsSize, size = 64; for (int i = 0; i < numsSize; i++) if (nums[i] > 0) { flag = i; break; } if (flag == 0 || flag > numsSize - 2) flag = numsSize - 2; int **arrys = (int **)malloc(size * sizeof(int *)); *returnSize = 0; for (int i = 0; i < flag; i++) { int start = i + 1, end = numsSize - 1; if (i > 0 && nums[i] == nums[i - 1]) continue; while (start < end) { int sum = nums[i] + nums[start] + nums[end]; if (sum== 0) { if (start > i + 1 && nums[start] == nums[start - 1]) { start++; continue; } arrys[*returnSize] = (int*)malloc(3 * sizeof(int)); arrys[*returnSize][0] = nums[i]; arrys[*returnSize][1] = nums[start]; arrys[*returnSize][2] = nums[end]; printf("%d %d %d\n", arrys[*returnSize][0], arrys[*returnSize][1], arrys[*returnSize][2]); (*returnSize)++; if (size == *returnSize) { size <<= 1; arrys = (int **)realloc(arrys, sizeof(int *) * size); } start++; end--;//因为是从小到大排序，start 增大则第 3 个数需要减小 continue; } else if (sum > 0) end--; else { start++;// end = numsSize - 1; } } } return arrys; }
2019-02-12