常见算法（1）

layout: post

title: '常见算法（1）'

subtitle: '转载请注明出处'

date: 2019-08-29

categories: Android Java 算法

cover: 'http://bpic.588ku.com/back_pic/05/61/11/465b46e23671e61.jpg'

tags: Android Java 算法

---

二叉树的深度优先遍历和广度优先遍历的具体实现

public class Tree {
    Tree left, right;
    int data;
    public Tree(int data) {
        this.data = data;
    }
 
}
//深度优先遍历（其实和前序遍历实现一样）
public void queryByDeepth(Tree root) {
    if(root != null) {
        print(root.data);
    }
    if(root.left != null) queryByDeepth(root.left);
    if(root.right != null) queryByDeepth(root.right);
}
 
//广度优先遍历（用队列辅助实现）
public void queryByDeepth(Tree root) {
    if(root == null) return;
    Queue<Tree> queue = new LinkedList<Tree>();
    queue.offer(root);
    while(root != null || !queue.isEmpty()) {
        root = queue.poll();
        print(root.data);
        if(root.left != null) queue.offer(root.left);
        if(root.right != null) queue.offer(root.right);
    }
    
}

手写链表逆序代码

//假设LinkedList的结点是Node
//1、遍历法
public Node reverseLinkedList(LinkedList head) {
    if(head == null || head.next == null) return head;
    Node pre = null, next = null;
    while(head != null) {
        next = head.next;
        next.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
//2、递归法
public Node reverseLinkedList(LinkedList head) {
    if(head == null || head.next == null) return head;
    Node next = head.next;
    Node newNode = reverseLinkedList(next);
    next.next = head;
    head.next = null;
    return newNode;
}

判断单链表成环与否？

public boolean linkHasCircle(LinkedList node) {
    if(node == null || node.next == null) return false;
    Node first = node, second = node;//first慢指针一次走一步；second快指针一次走两步
    while(second.next != null && second.next.next != null) {
        first = node.next;
        second = node.next.next;
        if(first == second) {
            return true;
        }
    }
    return false;
}

合并多个单有序链表（假设都是递增的）

//这个主要遍历链表，比较值大小，如果需要返回链表头节点，则需要先把头结点保存好
public Node merge(LinkedList node1, LinkedList node2) {
    if(node1 == null) return node2;
    if(node2 == null) return node1;
    if(node1 == null && node2 == null) return null;
    int data1 = node1.data;
    int data2 = node2.data;
    Node newNode, head;
    int data = data2;
    if(data1 <= data2) {
        data = data1;
        node1 = node1.next;
    } else {
        node2 = node2.next;
    }
    newNode = new Node(data);
    head = newNode;
 
    while(node1 != null && node2 != null) {
        if(node1.data <= node2.data) {
            newNode.next.data = node1.data;
            node1 = node1.next;
        } else {
            newNode.next.data = node2.data;
            node2 = node2.next;
        }
        newNode = newNode.next;
    }
    while(node1 != null) {
            newNode.next.data = node1.data;
            node1 = node1.next;
            newNode = newNode.next;
    }
 
    while(node2 != null) {
            newNode.next.data = node2.data;
            node2 = node2.next;
            newNode = newNode.next;
    }
    return head;
}