数据结构中的循环链表（Java详解版）

循环单链表（Circular Linked List，简称循环链表）是一种首尾相连的单链表。

在线性链表中，每个结点的指针都指向它的下一个结点，最后一个结点的指针域为空，不指向任何结点，仅表示链表结束。若把这种结构改变一下，使最后一个结点的指针域指向链表的第一个结点，就构成了循环链表。

图 1 循环单链表为空时的情况

若循环单链表带头结点为空，则 head.next==head。

有时为了操作方便，在循环单链表中只设置尾指针 rear 而不设置头指针，利用 rear 指向循环单链表的最后一个结点，如下图所示。

图 2 只设置尾指针的循环单链表

利用尾指针可以使有些操作变得简单，如图 3 所示：

图 3 设置尾指针的循环单链表LA和LB

要将两个循环单链表（尾指针分别为 LA 和 LB）合并成一个链表，只需要将一个表的表尾和另一个表的表头连接即可，如下图所示：

图 4 两个设置尾指针的循环单链表合并后

合并两个设置尾指针的循环单链表需要 3 步操作：

保存 LA 的头指针，即 p=LA.next。
把 LA 的表尾与 LB 的第一个结点相连接，即 LA.next=LB.next.next。
把 LB 的表尾与 LA 的表头相连接，即 LB.next=p。

最后多余的 LB 的表头结点会自动被释放。

循环单链表的应用：约瑟夫问题

有 n 个人，编号为 1、2、…、n，围成一个圆圈，按照顺时针方向让编号为 k 的人从 1 开始报数，报数为 m 的人出列，他的下一个人重新开始从 1 报数，报到 m 的人出列，一直这样重复下去，直到所有的人都出列。

要求编写一个算法，输入 n、k 和 m，依次输出每次出列的人的编号。

解决约瑟夫问题可以分为 3 个步骤：

建立一个具有 n 个结点的不带头结点的循环单链表，编号从 1 到 n，代表 n 个人。
找到第 k 个结点，即第一个开始报数的人。
编号为 k 的人从 1 开始报数，并开始计数，报数为 m 的人出列，即删除该结点。从下一个结点继续开始报数，重复执行步骤（2）和步骤（3），直到最后一个结点被删除。

约瑟夫问题的算法描述如下：

复制纯文本复制

public void Josephus(int n, int m, int k) {
    //在由n个人围成的圆圈中，从第k个人开始报数，数到m的人出列
    ListNode p = head, q = null;
    for (int i = 1; i < k; i++) //从第k个人开始报数
    {
        q = p;
        p = p.next;
    }
    while (p.next != p) {
        for (int i = 1; i < m; i++) //数到m的人出列
        {
            q = p;
            p = p.next;
        }
        q.next = p.next; //将p指向的结点删除，即报数为m的人出列
        System.out.print(String.format("%4d", p.data));
        p = q.next; //p指向下一个结点，重新开始报数
    }
    System.out.println(String.format("%4d", p.data));
}
 
public void CreateCycList(int n) {
    //创建循环单链表
    ListNode s, r = null;
    for (int i = 1; i < n + 1; i++) {
        s = new ListNode(i);
        if (head == head.next)
            head = s;
        else
            r.next = s;
        r = s;
    }
    r.next = head;
}
 
public static void main(String args[]) {
    CircularLinkList L = new CircularLinkList();
    Scanner sc = new Scanner(System.in);
    System.out.print("输入圈中人的个数：");
    int n = sc.nextInt();
    System.out.print("输入开始报数的序号：");
    int k = sc.nextInt();
    System.out.print("报数为m的人出列：");
    int m = sc.nextInt();
    L.CreateCycList(n);
    L.Josephus(n, m, k);
}

public void Josephus(int n, int m, int k) {
    //在由n个人围成的圆圈中，从第k个人开始报数，数到m的人出列
    ListNode p = head, q = null;
    for (int i = 1; i < k; i++) //从第k个人开始报数
    {
        q = p;
        p = p.next;
    }
    while (p.next != p) {
        for (int i = 1; i < m; i++) //数到m的人出列
        {
            q = p;
            p = p.next;
        }
        q.next = p.next; //将p指向的结点删除，即报数为m的人出列
        System.out.print(String.format("%4d", p.data));
        p = q.next; //p指向下一个结点，重新开始报数
    }
    System.out.println(String.format("%4d", p.data));
}

public void CreateCycList(int n) {
    //创建循环单链表
    ListNode s, r = null;
    for (int i = 1; i < n + 1; i++) {
        s = new ListNode(i);
        if (head == head.next)
            head = s;
        else
            r.next = s;
        r = s;
    }
    r.next = head;
}

public static void main(String args[]) {
    CircularLinkList L = new CircularLinkList();
    Scanner sc = new Scanner(System.in);
    System.out.print("输入圈中人的个数：");
    int n = sc.nextInt();
    System.out.print("输入开始报数的序号：");
    int k = sc.nextInt();
    System.out.print("报数为m的人出列：");
    int m = sc.nextInt();
    L.CreateCycList(n);
    L.Josephus(n, m, k);
}

程序运行结果如下：

输入圈中人的个数：9
输入开始报数的序号：3
报数为m的人出列：5
7 3 9 6 5 8 2 4 1

数据结构中的循环链表（Java详解版）

循环单链表的应用：约瑟夫问题

相关文章