程序员代码面试指南 2.6：环形链表的约瑟夫问题

解法一

1、思路

• 遍历环形链表，删除每 m 个节点，直到链表中剩下一个元素为止；

• 一共要删除 n - 1 个节点，每次删除要遍历 m 次，时间复杂度为 ，略高。

2、代码

#include <iostream>
#include <memory>

using namespace std;

struct ListNode                         //单链表结构体
{
    int val;
    shared_ptr<ListNode> next;
    ListNode(int _val) : val(_val), next(nullptr) {}
};

shared_ptr<ListNode> createList(int n)  //构造环形链表
{
    shared_ptr<ListNode> head = make_shared<ListNode>(0);
    auto p = head;

    for (int i = 1; i <= n; ++ i)
    {
        p = p->next = make_shared<ListNode>(i);
    }

    p->next = head->next;
    return head->next;
}

//约瑟夫环问题，每次删去环中第m个节点
shared_ptr<ListNode> josephusKill(shared_ptr<ListNode> head, int m)
{
    if (head == nullptr || head->next == head || m < 1) return head;

    auto last = head;
    while (last->next != head)  //保存最后一个节点
    {
        last = last->next;
    }

    int cnt = 0;
    while (head != last)        //当 head == last 时，链表中只剩下一个节点了
    {
        if ( ++ cnt == m)       //跳过每 m 个节点
        {
            last->next = last->next->next;
            cnt = 0;
        }
        else
        {
            last = last->next;
        }

        head = last->next;
    }

    return head;
}

int main()
{
    int n, m;
    cin >> n >> m;

    shared_ptr<ListNode> head = createList(n);

    while (head->next->val != head->val)    //循环删除，直到剩下一个节点为止
    {
        head = josephusKill(head, m);
    }

    cout << head->val << endl;

    return 0;
}