链表

节点链接，不一定连续存放

带/不带 头结点

1.单链表

1.1定义

//定义节点类
class ArrayNode {
    //定义节点属性
    public String name;
    public boolean isMale;
    private int weight;
    private int height;
    //next域
    public ArrayNode next;

    //构造器
    public ArrayNode(String name, boolean isMale, int weight, int height) {
        this.name = name;
        this.isMale = isMale;
        this.weight = weight;
        this.height = height;
    }

    @Override
    public String toString() {
        return "ArrayNode{" +
                "name=‘" + name + ‘\‘‘ +
                ", isMale=" + isMale +
                ", weight=" + weight +
                ", height=" + height +
                ‘}‘;
    }

}

//定义链表类
class ArrayNodeList {
    //定义头结点
    private ArrayNode head = new ArrayNode("二狗", true, 80, 180);

    //添加节点
    //最后一个节点的next指向新节点
    public void add(ArrayNode node) {
        //辅助节点，用于遍历
        ArrayNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            } else {
                temp = temp.next;
            }
        }
        temp.next = node;
    }
	//增删改查操作
    //类似于指针操作
    //
    //显示链表
    public void list() {
        //判空
        if (head.next == null) {
            return;
        }
        //遍历
        ArrayNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }    
}

1.2 翻转链表

/**
*将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
*如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样
*你不能更改节点中的值，只能更改节点本身。
*要求空间复杂度O(1)

 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || head.next == null || k == 1){
            return head;
        }
        //头结点及辅助节点
        ListNode nh = new ListNode(0);
        nh.next = head;
        ListNode p = nh;
        ListNode q = head,temp = head;
        //先计算出长度
        int num = 0;
        while(temp != null){
            num++;
            temp = temp.next;
        }
        //
        for(int i = 0;i < num/k;i++){
            //利用头插法，K链表的首节点设标记q，q依次后移，同时
            //每次都把q后面的一个移到p后面，而p不变
            for(int j = 1;j < k;j++){
                temp = q.next;
                q.next = temp.next;
                temp.next = p.next;
                p.next = temp;
            }
            //一轮翻转后，再改变p,q
            p = q;
            q = q.next;
        }
        return nh.next;
    }
}    

2.双向链表

//增加了前驱节点

3.环形链表

3.1 约瑟夫问题

//节点类
public class Kid {
    private int no;
    private Kid next;

    public Kid(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Kid getNext() {
        return next;
    }

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

//环形链表
public class CircleList {
    private Kid first = new Kid(-1);

    public void addKids(int num) {
        if (num < 1) {
            return;
        }
        //加入新节点
        Kid curKid = null;
        for (int i = 1; i <= num; i++) {
            Kid kid = new Kid(i);
            if (i == 1) {
                first = kid;
                first.setNext(first);
                curKid = first;
            } else {
                curKid.setNext(kid);
                kid.setNext(first);
                curKid = kid;
            }
        }
    }

    public void showKids() {
        if (first == null) {
            System.out.println("No Data");
        }
        Kid curKid = first;
        while (true) {
            System.out.println("No:" + curKid.getNo());
            if (curKid.getNext() == first) {
                break;
            }
            curKid = curKid.getNext();
        }
    }

    /**
     * @param start 表示从第几个小孩开始数
     * @param count 数的次数
     * @param num   最初有几个小孩
     */
    public void countKids(int start, int count, int num) {
        if (first == null || start < 1 || start > num) {
            System.out.println("Error Input");
            return;
        }
        //指向最后一个节点的指针
        Kid helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        //报数前让first和helper同时移动 k-1 次，定位到初始位
        for (int i = 0; i < start - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //报数时，同时移动 m-1 次，然后出队
        while (helper != first) {
            //移动count -1 次
            for (int i = 0; i < count - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first即为出队的小孩
            System.out.println("出：" + first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后一个：" + first.getNo());
    }
}

public class JosephuTest {
    /**
     * 编号1-n的小孩坐一圈，k号小孩从1开始报数，数到m的人出队，
     * 他的下一个人再从1开始报数，直到所有人出队，
     * 求出队编号序列
     */
    public static void main(String[] args) {
        //创建环形链表
        CircleList kids = new CircleList();
        kids.addKids(5);
        kids.showKids();
        kids.countKids(1,2,5);
    }
}

4.应用

3.链表

原文：https://www.cnblogs.com/fremontxutheultimate/p/14585087.html