一.单链表反转

单链表的反转，是面试中的一个高频题目

需求：

原链表中数据为： 1->2->3>4

反转后链表中数据为： 4->3->2->1

反转 API ：

public void reverse() ：对整个链表反转

public Node reverse(Node curr)：反转链表中的某个结点curr,并把反转后的curr结点返回

使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕。

代码 :

 public void reverse(){
        if(N==0){
            return;
        }

        reverse(head.next);

    }
    public Node reverse(Node curr){

        if(curr.next==null){
            head.next=curr;
            return curr;
        }

        //当前结点的上一个结点
        Node pre = reverse(curr.next);

        pre.next = curr;

        //当前结点的下一个结点设为null
        curr.next=null;
        //返回当前结点
        return curr;
    }

二.快慢指针

快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以然我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍。

1.中间值问题

利用快慢指针，我们把一个链表看成一个跑道，假设 a 的速度是 b 的两倍，那么当 a 跑完全程后， b 刚好跑一半，以此来达到找到中间节点的目的。

 /**
     * 快慢指针法，找到链表的中间结点
     */
    public Node findMiddleNode() {
        if (N == 0) {
            return null;
        }
        //定义快慢指针
        Node fast = head;
        Node slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

2.单向链表是否有环问题

使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。

  /**
     *  单向链表是否有环问题
     */
    public boolean hasCycle() {
        if (N == 0) {
            return false;
        }
        //定义快慢指针
        Node fast = head;
        Node slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

3.有环链表入口问题

当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1 ，则慢指针与 “ 新 ” 指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识，这里略，只讲实现。

    /**
     * 有环链表入口问题
     */
    public Node detectCycle() {
        if (N == 0) {
            return null;
        }
        //定义快慢指针
        Node fast = head;
        Node slow = head;

        //定义临时指针
        Node<String> temp = null;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //如果快慢指针相遇，说明有环
            if (fast == slow) {
                //让临时指针指向头结点
                temp = head;
                continue;
            }
            if (temp != null) {
                temp = temp.next;
                if (temp.equals(slow)) {
                    return temp;
                }
            }
        }
        return null;
    }

三.循环链表

循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为 null ，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。

四.约瑟夫问题

问题描述：

传说有这样一个故事，在罗马人占领乔塔帕特后， 39 个犹太人与约瑟夫及他的朋友躲到一个洞中， 39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，第一个人从 1 开始报数，依次往后，如果有人报数到3 ，那么这个人就必须自杀，然后再由他的下一个人重新从 1 开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16 个与第31 个位置，从而逃过了这场死亡游戏。

问题转换：

41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。

1.编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；

2.自退出那个人开始的下一个人再次从1开始报数，以此类推；

3.求出最后退出的那个人的编号。

图示：

解题思路：

1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；

2.使用计数器count，记录当前报数的值；

3.遍历链表，每循环一次，count++；

4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；

public class josephTest {
    public static void main(String[] args) {
        //1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；

        //构建首结点
        Node<Integer> first = null;

        //构建前一个结点
        Node pre = null;

        for (int i = 1; i <= 41; i++) {
            if (i == 1) {
                //记录首结点的值
                first = new Node<>(i, null);
                //让pre指向首结点
                pre = first;
                continue;
            }

            //构建新结点
            Node<Integer> newNode = new Node<>(i, null);
            pre.next = newNode;
            pre = newNode;

            if (i == 41) {
                //构建循环链表,让最后一个结点指向第一个结点
                pre.next = first;
            }
        }

        //2.使用计数器count，记录当前报数的值；
        int count = 0;

        //3.遍历链表，每循环一次，count++；
        Node n = first;

        Node before = null;

        while(n!=n.next){
            count++;
            if(count==3){
                //4.当count==3时，将当前结点从链表中删除；
                before.next=n.next;
                System.out.println(n.item);
                count=0;
            }
            before=n;
            n=n.next;
        }
        /*打印剩余的最后那个人*/
        System.out.println(n.item);
    }

五.总结

本文介绍了常见数据结构链表在开发中的常见应用形式，并用Java语言对其进行了实现。下文将介绍线性表中另一常见数据结构——栈。

本文含有隐藏内容，请开通VIP 后查看

线性表——链表（在开发中常见应用场景）