package com.appdemo;

import android.util.Log;

import java.util.Stack;

public class Node {


    int value;//节点内容
    Node next;//下一个节点

    public Node(int value) {
        this.value = value;
    }

打印链表

    public void show() {//输出所有节点
        Node currentNode = this;
        while (true) {
            Log.w("TAG", "---all---" + currentNode.value);
            //取出下一个节点
            currentNode = currentNode.next;
            //如果是最后一个节点
            if (currentNode == null) {
                break;
            }
        }
    }

判断链表是否有环形

首先创建两个指针1和2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

private void loop() {
    // 构造链表 1->2->3->4->5->6-4;
    Node a = new Node(1);
    Node b = new Node(2);
    Node c = new Node(3);
    Node d = new Node(4);
    Node e = new Node(5);
    Node f = new Node(6);
    a.next = b;   b.next = c;   c.next = d;
    d.next = e;
    e.next = f;
    //f.next = d;//构造环形  4    // a.show();//输出所有节点
     Log.w("TAG", "----" + isLoop(a));
}
public static boolean isLoop(Node head){
    Node slow = head.next;
    Node fast = head.next.next;
    // 链表为空或者只有一个节点
    if(slow == null || fast == null){
        return false;
    }
    while(slow.next != null){
        // 只有 两个节点，当然是不存在循环的
        if(fast.next == null){
            return false;
        }
        // 如果slow的数据域和fast的数据域相同，则表示有环
        if(slow.value == fast.value){
            return true;
        }
        // slow指针走一步，fast走两步
        slow = slow.next;
        fast = fast.next.next;
        //如果fast走到最后为空，表示没有环
        if(fast == null){
            return false;
        }
    }
    return false;
}

反转链表 递归

    public Node reverse(Node head) {
        //如果链表为空或者链表中只有一个元素
        if (head == null || head.next == null) {
            return head;
        }
        Node temp = head.next;
        ////先反转后面的链表，走到链表的末端结点
        Node newHead = reverse(head.next);
        //再将当前节点设置为后面节点的后续节点
        temp.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 1->2->3->4  原始链表
     * 1,从第二个数据开始，间第二个的指针指向第一个，比喻2->1
     * 2,将现有的头部  1转换成尾部，尾部的next为null
     * 3，将从第二个node开始，循环next指向前一个
     * 4，一直有个指针指向还没有反转的链表的头部
     * 需要左中右三个指针
     */
    public static Node reverseList(Node node) {
        Node pre = null;
        Node next = null;
        while (node != null) {
            next = node.next; //第二个节点
            node.next = pre;//2 null
            pre = node;//baocun  1 jiedian
            node = next;
            pre.show();//输出所有节点
            Log.w("TAG", "----------------");
        }
        return pre;
    }

删除某一个节点

    public void removeNode() {
        //通过当前节点找到下下一个节点
        Node newNext = next.next;
        //再把下一个节点赋值给当前节点的下一个节点
        this.next = newNext;
    }

插入某个节点,作为当前节点的下一个节点

    public void addNode(Node node) {
        //取出下一个节点，作为下下个节点
        Node nextNode = next;
        //把新节点作为单点节点的下一个节点
        this.next = node;
        //把下下个节点作为设置新节点的下一个节点
        node.next = nextNode;
    }

合并两个有序链表

    public Node Merge(Node list1, Node list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        Node pMergeHead = null;
        if (list1.value < list2.value) {
            pMergeHead = list1;
            pMergeHead.next = Merge(list1.next, list2);
        } else {
            pMergeHead = list2;
            pMergeHead.next = Merge(list1, list2.next);
        }
        return pMergeHead;
    }

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

    public Node FindKthToTail(Node head, int k) {
        Node pre = null, p = null;
        //两个指针都指向头结点
        p = head;
        pre = head;
        //记录k值
        int a = k;
        //记录节点的个数
        int count = 0;
        //p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，
        //当p指针跑到最后时，pre所指指针就是倒数第k个节点
        while (p != null) {
            p = p.next;
            count++;
            if (k < 1) {
                pre = pre.next;
            }
            k--;
        }
        //如果节点个数小于所求的倒数第k个节点，则返回空
        if (count < a) return null;
        return pre;
    }

两个栈实现一个队列

    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();

        public void push(int node) {
            stack1.push(node);
        }

        public int pop() {
            if (stack1.empty() && stack2.empty()) {
                throw new RuntimeException("Queue is empty!");
            }
            if (stack2.empty()) {
                while (!stack1.empty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

}