单链表

介绍：

　　1）有序的列表。

　　2）以节点的方式存储，是链式存储。

　　3）每个节点包含data域，next域：指向下一个节点。

　　4）链表的各个节点不一定是连续存储。

　　5）分为带头节点的链表和没有头节点的链表。

使用：

　　1.求单链表中有效节点个数

　　答：遍历链表。

　　2.查找单链表中倒数第k个节点

　　答：先遍历链表，得出总长，再遍历找出倒数第k个元素

　　3.单链表的反转

　　答：1）新建一个单链表，遍历原单链表，每一个元素放到新单链表的头。

　　　　2）使用stack，利用stack先进后出的特性。

缺点：

　　1）查找只能是一个方向。

　　2）不能自我删除，需要靠辅助节点。

双链表

介绍：

　　1）遍历方式与单链表相同，可以向前，也可以向后

　　2）添加（默认天加到双向链表的最后）

　　　　i.先找到双向链表的最后节点

　　　　ii.temp.next = newNode

　　　　iii.newNode.pre = temp

　　3）修改，与单链表思路相同

　　4）删除，能够自我删除

　　　　i.temp.pre.next = temp.next

　　　　ii.temp.next.pre = temp.pre

单向环形链表

场景：Josephu（约瑟夫、约瑟夫环）问题

　　　　问题：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。

代码如下：

public class Josephu { 
    public static void main(String[] args) {      
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();  
        circleSingleLinkedList.addBoy(5);  
        circleSingleLinkedList.shwBoy();  
        circleSingleLinkedList.countBoy(1, 3, 5);  
    }
}
class CircleSingleLinkedList 
{ 
    private Boy first = null;
    
    public void addBoy(int nums) {      
        if (nums < 1) {      
            System.out.println("nums的值不正确");  
            return;  
        }  
        Boy curBoy = null;  
        for (int i = 1; i <= nums; i ++) {      
            Boy boy = new Boy(i);     
            if (i == 1) {      
                first = boy;     
                first.setNext(first);     
                curBoy = first;  
            } else {      
                curBoy.setNext(boy);     
                boy.setNext(first);     
                curBoy = boy;  
            }  
        }  
    }
    
    public void shwBoy() {      
        if (first == null) {      
            System.out.println("没有数据");     
            return;  
        }  
        Boy curBoy = first;     
        while (true) {      
            System.out.printf("小孩的编号 %d\n", curBoy.getNo());     
            if (curBoy.getNext() == first) {      
                break;  
            }  
            curBoy = curBoy.getNext();  
        }  
    }
    
    public void countBoy(int startNo, int countNum, int nums) {      
        if (first == null || startNo < 1 || startNo > nums) {      
            System.out.println("参数输入有误，请重新输入");     
            return;  
        }  
        Boy helper = first;
        
        while (true) {      
            if (helper.getNext() == first) {      
                break;  
            }  
            helper = helper.getNext();  
        }
        
        for (int j = 0; j < startNo - 1; j ++) {      
            first = first.getNext();     
            helper = helper.getNext();  
        }
        
        while (true) {      
            if (helper == first) {      
                break;  
            }  
            for (int j = 0; j < countNum - 1; j ++) {      
                first = first.getNext();     
                helper = helper.getNext();  
            }  
            System.out.printf("%d\n", first.getNo());     
            first = first.getNext();     
            helper.setNext(first);  
        }  
        System.out.printf("11%d\n", first.getNo());
    
    }
}
class Boy { 
    private int no;
    private Boy next;
    public Boy(int no) {      
        this.no = no;  
    }  
    public int getNo() {      
        return no;  
    }  
    public void setNo(int no) {      
        this.no = no;  
    }  
    public Boy getNext() {      
        return next;  
    }  
    public void setNext(Boy next) {      
        this.next = next;  
    }
}

View Code

思路：构建一个单项环形链表。first是头，rear是尾。从第k个报数，first和rear就要先移动k-1个位置。数到m的出列，while循环，每次移动m-1个位置，first就是要出列的，再指向下一位，first = first.next  rear.next = first