哈哈，被提名了，谢谢老师。

有兴趣的同学可以把你的答案分享到 Github: https://github.com/iostalks/Algorithms

有问题也可以在 issue 中一起讨论。

新的一年跟大家一起进步，一起流弊。

Java语言实现一个大小固定的有序数组，支持动态增删改操作
代码如下:
public class Array {
    private String[] data;
    private int count;
    privvate int size;
    public Array(int capacity) {
        data = new String[capacity];
        count = 0;
        size = capacity;
    }
    public boolean insert(int index, String value) {
        if (count >= size) {
            return false;
        }
        if (index < 0 || index > count) {
            return false;
        }
        for (int i = count - 1;i >= index;i--) {
             data[i+1] = data[i];
        }
        data[index] = value;
        count++;
    }
    public String delete(int index, String value) {
        if (count == 0) {
            return false;
        }
        if (index < 0 || index >count) {
             return false;
         }
        value = data[index];
        for (int i = index;i <= count - 1;i++) {
            data[i - 1] = data[i];
        }
        count--;
        return value;
}

合并有序数组 go 语言实现
package main

import "fmt"

func mergeOrderedArray(a, b []int) (c []int) {
    i, j, k := 0, 0, 0
    mergedOrderedArrayLength := len(a) + len(b)
    c = make([]int, mergedOrderedArrayLength)
    for {
        if i >= len(a) || j >= len(b) {
            break
        }

        if a[i] <= b[j] {
            c[k] = a[i]
            i++
        } else {
            c[k] = b[j]
            j++
        }
        k++
    }

    for ; i < len(a); i++ {
        c[k] = a[i]
        k++
    }

    for ; j < len(b); j++ {
        c[k] = a[j]
        k++
    }

    return
}

func main() {
    a := []int{1, 3, 5, 7, 9, 10, 11, 13, 15}
    b := []int{2, 4, 6, 8}
    fmt.Println("ordered array a: ", a)
    fmt.Println("ordered array b: ", b)
    fmt.Println("merged ordered array: ", mergeOrderedArray(a, b))
}

java实现一个动态扩容的数组（扩容2倍）
代码如下:
package array;

public class DynamicArray {
    
    private String[] data;
    private int count;
    private int size;
    
    public DynamicArray(int capacity) {
        data = new String[capacity];
        count = 0;
        size = capacity;
    }
    
    public String[] expand(String[] data) {
        if (count >= size) {
            String[] newArray = new String[this.size * 2];
            this.size = this.size * 2;
            for (int i = 0;i < count;i++) {
                newArray[i] = this.data[i];
            }
            return newArray;
        } else {
            return this.data;
        }
    }
    
    public boolean append(String item) {
        if (count >= size) {
            this.data = expand(this.data);
        }
        this.data[count] = item;
        count++;
        return true;
    }
    
    public void printAll() {
        for (int i = 0;i < count;i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray(5);
        for (int i = 0;i < dynamicArray.size;i++) {
            dynamicArray.data[i] = "This value is " + i;
            dynamicArray.count++;
        }
        dynamicArray.append("This value is 5");
        System.out.println("Now the size of data is " + dynamicArray.size);
        dynamicArray.printAll();
    }
  
}

求众数
解题思路：将数组排序，统计每个数字出现的次数，当满足众数条件时返回。时间复杂度 nlogn

int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
int majorityElement(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int), compare);
    int num = nums[0],flag=numsSize>>1,count=1;
    for (int i = 1; i < numsSize; i++)
    {
        if (nums[i] != num)
        {
            num = nums[i]; count = 1;
        }
        else
        {
            count++;
        }
        if (count > flag)
            break;
    }
    return num;
}
更优解

数组元素为奇数个，众数数量大于半数，所以相互抵消后最后剩余的一定为众数，时间复杂度 O(n)

int majorityElement(int* nums, int numsSize)
{
    int count = 1,num=nums[0];
    for (int i = 1; i < numsSize; i++)
        if (count == 0 || num == nums[i])
        {
            count++; num = nums[i];
        }
        else
            count--;
    return num;
}

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

3. 实现求链表的中间结点
public class FindMidNode {

    // 1. T(n) = O(2*n) 遍历2次
    public static Node findMidNode(Node head) {
        if (head == null) {
            return null;
        }

        int len = 0;
        Node p = head;

        while(p != null) {
            len++;
            p = p.next;
        }

        p = head;
        for (int i = 0; i < len/2; i++) {
            p = p.next;
        }

        return p;
    }

    // 2. T(n) = O(n) 遍历1次
    // 快慢指针法
    public static Node findMidNodeFast(Node head) {
        if (head == null) {
            return null;
        }

        Node fast = head;
        Node slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }


    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static class Node {
        public int data;
        public Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

4. Linked List Cycle I（环形链表）
/**
 * 141. Linked List Cycle
 * https://leetcode.com/problems/linked-list-cycle/
 */
public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }

        return false;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }
}

1. 实现单链表反转：
/**
 * 206. Reverse Linked List
 * https://leetcode.com/problems/reverse-linked-list/
 */
public class ReverseList {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            this.val = val;
        }
    }
}

2. 实现两个有序的链表合并为一个有序链表
/**
 * 21. Merge Two Sorted Lists
 * https://leetcode.com/problems/merge-two-sorted-lists/
 */
public class Merge2SortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
    
    // 利用哨兵（前哨节点）简化实现难度
        ListNode outpost = new ListNode(-1);
        ListNode temp = outpost;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next;
        }

        if (l1 == null) {
            temp.next = l2;
        }

        if (l2 == null) {
            temp.next = l1;
        }

        return outpost.next;
    }
    
    public ListNode mergeTwoListsRecur(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoListsRecur(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoListsRecur(l1, l2.next);
            return l2;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }
}

1.Three Sum：暴力匹配三元组，三层循环结束后打印保存三元组的数组即可，时间复杂度O（n^3），空间复杂度O（n）。简化一下，为减少比较次数先排序。外层循环i遍历数组，内层循环从数组两头元素（s、t）开始考察，找出使num【s】+num【t】=-num【i】的s和t，若大了t- -，若小了s++（内层要避开i）s大于等于t则匹配失败。这样两层循环就可以了，时间复杂度O（n^2）。

2.Majority Element：重点在于统计每个元素出现次数，可以先排序，然后顺序计算出每个数的出现次数，与阈值比较，大于则输出，时间复杂度O（nlogn）。也可以采用散列表，把每个元素存入散列表，并记录出现次数，最后把出现次数超过阈值的元素输出即可，时间复杂度O（n），空间复杂度O（n）。

3.Missing Positive：本来想用散列表，发现要求时间复杂度O（n），空间复杂度为常量，有点捉急。只能从原数组上做文章。假设数组A长度为n，若i为1到n的正整数，若i存在于A中，我们就把它的位置调整到A【i-1】处，这样通过A【i】是否为i+1即可知道i+1是否在数组中。那么A中不满足上述条件的最小下标+1即为缺失的最小正整数值。

4. Linked List Cycle I（环形链表）：用图的拓扑排序算法可以，但是要统计顶点出入度，空间复杂度无法达到O（1）。那可以用快慢指针，*fast以*slow的两倍速前进，如果fast和slow重合则说明有环。

5. Merge k Sorted Lists（合并 k 个排序链表）：两两硬生生合并，时间复杂度应该是O（kN），再高级的方法想不出来。ps：如果可以抛弃原来的链表，那么新建一个合并后链表的时间复杂度可以是O（N）吧？N是k个链表的总长。

//单链表反转（带头结点）
void reverse(struct node* head){
    struct node* L;
    struct node* p;
    struct node* p2;
    struct node* p3;
    L = head->next;
    if(head == NULL){
        printf("链表未创建");
    }else if(L->next==NULL){
        printf("单链表只有一个节点，无需反转");
        return;
    }else if(L->next->next == NULL){
        head->next = L->next;
        head->next->next = L;
        L->next = NULL;
        printf("单链表反转成功");
    }else{
        p = L;
        p2 = L->next;
        p3 = L->next->next;
        while(p3!=NULL){
            p2->next = p;
            p = p2;
            p2 = p3;
            p3 = p3->next;
        }
        p2->next = p;
        L->next = NULL;
        head->next = p2;
        printf("单链表反转成功");    
    }
}

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
}