通过递归实现创建一个链表

Node节点的定义

public class Node {
    private final int value;
    private Node next ;
    public Node(int value)
    {
        this.value = value;
        next = null;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public static void printLinkedList(Node node)
    {
        while (node!=null)
        {
            System.out.print(node.getValue());
            System.out.print(" ");
            node = node.getNext();

        }
        System.out.println();

    }
}

递归创建链表

public Node createLinkedList(List<Integer> data)
    {
        if (data.isEmpty())
        {
            return  null;
        }
        Node firstNode = new Node(data.get(0));
        firstNode.setNext(createLinkedList(data.subList(1,data.size())));
        return firstNode;
    }

给定value值删除链表中出现的所有节点，存在多个相同节点的情况。

注意点：

• 头节点就出现匹配的数据，而且不止一个
• 删除节点的思想：改变next的指向
• 找出共同处理的地方使用循环的思想解决

    public Node deleteIfValue(Node head,int value){

        //特殊情况，头节点存在匹配value的情况
        while (head!=null&&head.getValue()==value)
        {
            head = head.getNext();
        }
        if (head==null)
        {
            return null;
        }
        //定义出一个指针
        Node pre = head;
        while (pre.getNext()!=null)
        {
            if (pre.getNext().getValue()==value)
            {
                pre.setNext(pre.getNext().getNext());
            }else {
                pre = pre.getNext();
            }
        }
        return head;
    }

利用两个栈实现一个队列的操作

栈的存储特点是后进先出，所以两个栈一个作为压栈使用，另一个作为弹出，但是要注意的一点就是需要保证栈1的元素都完全倒入到栈2中。

两个各司其职的栈

• 如果stackPush要往stackPop中压入数据，那么久必须把stackPush中的元素全部压入。
• 如果stackPop中不为空，那么就不可以往stackPop压入元素。

public class StackQueue {

    public Stack<Integer>   stackPush;
    public Stack<Integer>   stackPop;

    public StackQueue()
    {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

    //队列进队
    public void add(Integer i)
    {
        stackPush.push(i);
    }

    //队列的poll方法
    public int poll()
    {
        if (stackPop.empty()&&stackPush.empty())
        {
            System.out.println("队列为空。");
        }
        else if (stackPop.empty())
        {
            while (!stackPush.empty())
            {
                stackPop.push(stackPush.pop());
            }

        }
        return  stackPop.pop();

    }

    //队列的peek方法
    public int peek()
    {
        if (stackPop.empty()&&stackPush.empty())
        {
            System.out.println("队列为空。");
        }else if (stackPop.empty())
        {
            while (!stackPush.empty())
            {
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.peek();
    }
}

判断一个链表是不是回文的结构

题目：给定一个链表的头结点head，请判断该链表是不是回文的结构？
解决思路：利用栈的存储后进先出的特点进行回文的判定

//链表节点的定义
class LinkedNode
{
    int value;
    LinkedNode next = null;
    LinkedNode(int value)
    {
        this.value = value;
    }
}

    public boolean isPalindrome(LinkedNode head)
    {
        if (head==null){
            return  false;
        }
        Stack<Integer> stack = new Stack<Integer>();
        LinkedNode cur = head;
        //将链表的数据压入栈中
        while (cur!=null)
        {
           stack.push(cur.value);
           cur = cur.next;
        }

        //出栈进行回文判断
        while (head!=null)
        {
            if (head.value!=stack.pop())
            {
                return false;
            }
            head = head.next;
        }

        return true;
    }

删除一个链表中重复出现的节点

题目： 给定一个无序单链表的头节点head，删除其中值重复出现的节点。
例如：1->2->3->3->4->4->2->1->1->null，删除值重复的节点之后为
1->2->3->4->2->1->null

解决思路：

• 生成一个哈希表，因为头节点是不用删除的节点，所以首先将头节点的值存放入哈希表
• 从头节点的下一个节点开始往后遍历节点，假设当前遍历到cur节点，先检查cur的值是否在哈希表中，如果在，则说明cur节点的值是之前出现过的，就将cur节点删除，删除的方式是将最近一个没有被删除的节点pre连接到cur的下一个节点，即pre.next = cur.next.如果不在，将cur节点的值加入哈希表，同时令pre=cur，即更新最近一个没有被删除的节点。

    public void DeleteListNode(LinkedNode head)
    {
        //如果头结点是空的话结束程序
        if (head==null)
        {
            return ;
        }

        //初始化
        LinkedNode pre = head;
        LinkedNode cur = head.next;

        HashSet<Integer> set = new HashSet<Integer>();
        set.add(head.value);
        while (cur!=null)
        {
            if (set.contains(cur.value))
            {
                pre.next = cur.next;
            }
            else
            {
                set.add(cur.value);
                pre = cur;
            }
            cur = cur.next;
        }

打印两个有序链表的公共节点

题目：提供两个有序链表的头指针head1和head2，打印两个链表的公共部分。

    public void print(LinkedNode head1,LinkedNode head2)
    {
        while (head1!=null&&head1!=null)
        {
            if (head1.value<head2.value)
            {
                head1=head1.next;
            }else if (head1.value>head2.value)
            {
                head2=head2.next;
            }else
            {
                System.out.println(head1.value);
                head1 = head1.next;
                head2 = head2.next;
            }
        }

    }

反转链表

题目：输入一个链表，反转链表后，输出链表的所有元素。

解题思路：

• 当前节点是head，pre为当前节点的前⼀节点，next为当前节点的下⼀节点
• 需要pre和next的⽬目的是让当前节点从pre->head>next1->next2变成pre<-head next1->next2
• 先保存head.next的节点，然后将head.next=pre换成前一个节点的引用
• 然后pre = head,head = next，进行节点的遍历替换
• 如果head为null的时候，pre就为最后一个节点了了，但是 链表已经反转完毕，pre就是反转后链表的第一个节点

    public LinkedNode reverse(LinkedNode head)
    {

        if (head==null)
        {
            return null;
        }

        //初始化前后指标节点
        LinkedNode pre = null;
        LinkedNode next = null;
        while (head!=null)
        {
            next = head.next;
            head.next = pre;
            //head--> null

            pre = head;
            head = next;
        }

        return pre;
    }

输入一个链表，输出该链表中倒数第k个结点。

• 这道题的难点在于不不知道k结点的位置。
• 我们可以使⽤用两个指针，第一个指针先跑k-1 ,然后两个指针再一起跑
• 等到第一个指针到终点时，第二个指针距终点也就是倒数第k个结点

定义两个指针，我们都知道倒数第k个距离最后一个的距离是k-1，所以可以先移动一个指针走k步后，然后两个指针同时移动，那么在快的指针到达结尾时，慢的指针到达的位置正好是倒数第k个。

    public LinkedNode FindKthNode(LinkedNode head,int k)
    {

        //定义两个指针
        LinkedNode point1 = head;
        LinkedNode point2 = head;

        int a = k;//记录k值的变化
        int count = 0;//记录节点的数目


        while (point1!=null)
        {
            point1 = point1.next;
            count++;
            if (k<1) //说明此事point1已经到正向k的位置
            {
                point2 = point2.next; //指针2开始
            }
            k--; //point1每次走一次都要减去1
        }

        if (count<a)
            //如果节点个数⼩小于所求的倒数第k个节点，则返回null
        {
            return null;
        }

        return  point2;
    }

附加

二分查找

注意点：

• mid的计算方式采用a+(b-a)/2
• 理由是：当a和b的值过大的情况会出现溢出的情况，所以这里采用改进

  public static int binSearch(int[] arr,int k){
        int low = 0;
        int high = arr.length;
        //注意high的取值是arr.length或arr.length-1,对于循环体的处理不同
        while (high>low)
        {
            int mid = low+(high-low)/2; //(low+high)/2 当两个数很大的情况可能出现溢出
            if (arr[mid]>k)  // [low,mid)
            {
                high = mid;
            }else if (arr[mid]<k)
            {
                low = mid+1;
            }else 
                  return mid;
        }
        return -1;
    }

树的定义

package com.joyo.code;

public class TreeNode {
    private final char value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

创建树

二叉树

public TreeNode treeCreator()
    {
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.setRight(new TreeNode('C'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }

树的遍历（前序、中序、后序）

主要还是通过递归的思想来进行遍历，前中后就是调整语句的执行顺序

前序

 //前序遍历
    public static void  preOrder(TreeNode root){
        if (root==null)
        {
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

中序

  //中序遍历
    public void inOrder(TreeNode root){
        if (root==null)
        {
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());
    }

后序

//后续遍历
    public void postOrder(TreeNode root){
        if (root==null)
        {
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }

输出结果：
前序：ABDEGCF
中序：DBGEACF
后序：DGEBFCA

根据前序中序输出后序

注意点：

• 缩小范围，寻找递归的执行区域

• 前序和中序可以确认树的结构，但是前序和后序无法唯一性确定好二叉树的结构

  
  
  递归缩小求解范围

public String postPrint(String pre,String in){
        if (pre.isEmpty()){
            return "";
        }
        char rootNode = pre.charAt(0);
        int indexNode = in.indexOf(rootNode);
        return postPrint(pre.substring(1,indexNode+1),in.substring(0,indexNode))+
                postPrint(pre.substring(indexNode+1),in.substring(indexNode+1))+
                rootNode;
    }