算法类

1、链表

1.1链表的反转：

Public void reverse(Node node) {

Node now = node;

Node prev = null;

While(now != null) {
Node next = now.next;

  now.next = prev;

  prev = now;

  now = next;

return prev;

1.2合并两个有序链表

//非递归

public class Solution {

    public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){

            return list2;

        }

        if(list2 == null){

            return list1;

        }

        ListNode current = new ListNode(-1);//创建一个当前指针

        ListNode root = current;//头结点

        while(list1 != null && list2 != null){//当两个链表都不空时

        if(list2.val >= list1.val){//如果第二个链表当前的数值不小于第一个链表当前的数值

                current.next = list1;//将第一个链表的当前节点加入合并后的链表中

                current = list1;//当前指针后移

                list1 = list1.next;//第一个链表指针后移

            }else{

                current.next = list2;

                current = list2;

                list2 = list2.next;                

            }

        }

        if(list1 != null){

            current.next = list1;

        }

        if(list2 != null){

            current.next = list2;

        }

        return root.next;

    }

}

//递归

public class Solution {

    public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){

            return list2;

        }

        if(list2 == null){

            return list1;

        }

        ListNode head = null;

        if(list1.val <= list2.val){

            head = list1;

            head.next = Merge(list1.next,list2);

        }else{

            head = list2;

            head.next = Merge(list1,list2.next);

        }

        return head;

    }

}

2、树

判断树是不是对称的

public:

bool isTreeSymmertic(TreeNode *pHead1,TreeNode *pHead2){

if(pHead1==NULL && pHead2==NULL)

 return true;

 if(pHead1==NULL)

return false;

if(pHead2==NULL)

 return false;

Return(pHead1->val==pHead2->val)

&&isTreeSymmertic(pHead1->left,pHead2->right)

&&isTreeSymmertic(pHead1->right,pHead2->left);

 bool isSymmetrical(TreeNode* pRoot) {

if(pRoot==NULL)

return true;

bool res=isTreeSymmertic(pRoot->left,pRoot->right);

 return res;

3、两个数组合并

利用Arrays类的Array.asList()方法，另外一种是往新数组里放

方法1：

String[]  array1= {"a","b",""c};

String[]  array2= {"d","e"};

List list = new ArrayList(Arrays.asList(array1));

list.addAll(array2);

String[] newArray = new String[list.size()];

list.toArray(newArray);

for(int x=0;x

   System.out.print(str[x] + " ");

}

方法2：

String[]  array1= {"a","b",""c};

String[]  array2= {"d","e"};

String[] newArray = new String(array1.length + array2.length);

for(int i=0;i

newArray[i] = array1[x];

}

for(int j = 0; j

newArray[array1.length + j] = array2[j];

}

for(int k=0;k

 System.out.println(newArray[k]);

}

4、二分查找代码（可用递归和非递归方式实现）：

递归

//假定数组是按照从小到大有序

public static int search(int[] data,int from,int to,int target) {

if(from

    int mid = from+(to-from)/2;//防止溢出

if(data[mid] < target) {

return search(data,mid+1,to,target );

}else if(data[mid] > target){

return search(data,from, mid-1,target);

}else {

return mid;

}

}

return -1;

}

迭代

public static int search(int[] data,int from,int to,int target){

while(from < to){

   int mid = from + (to-from)/2;

   if(data[mid]

       from = mid +1;

   }else if(data[mid]>target){

   to = mid -1;

   }else {

   return mid;

   }

}

return -1

}

 5、快速排序

public void sort(int a[], int low, int high) {

int left = low;

int right = high;

//基准数

int pivot = a[left];

while(left

//从右往左找小于基准值的元素

while(left=pivot) {

right--;

a[left]=a[right];

//从左往右找大于基准值的元素

while(left

left++;

a[right]=a[left];

//以上操作完成后，基准值已经确定挖下的坑了，然后填数

a[left]=pivot;

//递归左边和右边

sort(a,low,left-1);

sort(a,left+1,high);

}

6、将二叉树转双向链表：

1、以最左节点作为头节点2、链表顺序为中序遍历3、不允许使用额外空间

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode(int val){
        this.val = val;
    }
}
public class Test5 {
    static TreeNode pre = null;
    static TreeNode cur = null;
    static TreeNode head = null;
    public static void main(String []args){
        inorder(n1);
    }

    public static void inorder(TreeNode root){
        if(root == null){
            return;
        }else {
            inorder(root.left);
            System.out.println(root.val);
            t(root);
            inorder(root.right);
        }
    }

    public static void t(TreeNode root){
        if(pre == null){
            pre = root;
            head = root;
            return;
        }else {
            cur = root;
        }
        System.out.println("pre : "+pre.val + "cur : " + cur.val);
        pre.right = cur;
        cur.left = pre;
        pre = cur;
    }
}