C++：06.反转单链表、实现ArrayList

1. 腾讯面试题：

1. 用 c/c++ 反转单链表

   • 输入: 1->2->3->4->5->NULL

   • 输出: 5->4->3->2->1->NULL

     struct ListNode *reverseList(struct ListNode* head) {
     	struct ListNode *newHead = NULL;
     	struct ListNode *node;
     	while (head != NULL) {
     		//1. 对之前的链表做头删
     		node = head;
     		head = head->next;
     		
     		//2. 对新链表做头插
     		node->next = newHead;
     		newHead = node;
     	}
     	return newHead;
     }

2. 用 c/c++ 判断一棵树是否为平衡二叉树 （可以是一棵空树，左右子树的高度差不会超过 1 ，并且左右两棵子树都是一棵平衡二叉树）

   /**
    *  判断一棵树是否是平衡二叉树
    */
   template <class T>
   bool isBalanceTree(TreeNode<T> *pNode){
       // 可以是一棵空树，左右子树的高度差不会超过 1 ，并且左右两棵子树都是一棵平衡二叉树
       if(!pNode)
           return true;
   
       // 左右子树的高度差不会超过 1
       int left = getDepthTree(pNode->left);
       int right = getDepthTree(pNode->right);
   
       // 并且左右两棵子树都是一棵平衡二叉树
       return abs(left-right) <= 1 && isBalanceTree(pNode->left) && isBalanceTree(pNode->right);
   }

2. ArrayList 源码分析

重点：如果开发中涉及到模板类，声明和实现要写到同一个类中，hpp = h + cpp/c (编译)

具体代码请看：NDKPractice项目的cpp20

或者请看： jni/20.C++基础-实现Native层的ArrayList

java中ArrayList知识点：

1. 如果未指定容量大小的话，默认容量是 10
2. 每次扩容都是扩充的原来的一半 oldCapacity + (oldCapacity >> 1);

代码：

#ifndef JNI20_ARRAYLIST_H
#define JNI20_ARRAYLIST_H

#include <malloc.h>
//------------------------ 声明 ------------------------//

template<class E>
class ArrayList {
private:
    // 长度，数组，当前交表
    E *array = NULL;      // 当前数组指针
    int len = 0;   // 数组大小
    int index = 0; // 当前角标
public:
    ArrayList();

    ArrayList(int len);

    ~ArrayList();

    ArrayList(const ArrayList& list);

    void add(E e);

    E remove(int index);

    E get(int index);

    int size();

private:
    void ensureCapacityInternal(int capacity);

    void grow(int capacity);
};

//------------------------ 实现 ------------------------//
template <class E>
ArrayList<E>::ArrayList() {}

// 每个方法都得添加
template <class E>
ArrayList<E>::ArrayList(int len) {
    if(len <= 0)
        return;
    this->len = len;
    this->array = (E*)malloc(sizeof(E)*len);
}

template <class E>
ArrayList<E>::~ArrayList() {
    if(this->array){
        free(this->array);
        this->array = NULL;
    }
}

template <class E>
ArrayList<E>::ArrayList(const ArrayList &list) {
    this->len = list.len;
    this->index = list.index;
    if(this->array){
       free(this->array);
    }
    this->array = malloc(sizeof(E)*list.len);
    memcpy(this->array,list.array, sizeof(E)*index);
}


template <class E>
int ArrayList<E>::size() {
    return this->index;
}

template <class E>
void ArrayList<E>::add(E e) {
    ensureCapacityInternal(index+1); // Increments modCount!!
    this->array[index++] = e;
}

template <class E>
void ArrayList<E>::ensureCapacityInternal(int capacity) {
    if(this->array == NULL)
        capacity = 10;
    if(capacity > this->len){
        // 创建新数组
        grow(capacity);
    }
}

template <class E>
void ArrayList<E>::grow(int capacity) {
    int new_len = len + (len >> 1); // 扩容 len的一半

    if(capacity > new_len){
        new_len = capacity;
    }

    // 创建新的数组
    E* new_array = (E*)malloc(sizeof(E)*new_len);

    if(this->array){
        memcpy(new_array,this->array,sizeof(E)* index); // sizeof(E)*index 字节
        // 释放旧的array
        free(this->array);
    }

    this->array = new_array;
    this->len = new_len;
}

template <class E>
E ArrayList<E>::get(int index) {
    return array[index];
}

template <class E>
E ArrayList<E>::remove(int index) {
    E e = array[index];
    int numMoved = this->index - index - 1;
    for(int i = index; i < index + numMoved ;i++){
        array[i] = array[i+1];
    }
    array[--this->index] = NULL;

    return e;
}


#endif // JNI20_ARRAYLIST_H