单链表实现约瑟夫环问题

时间:2021-12-28 11:24:20

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号123...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依规律重复下去,直到圆桌周围的人全部出列

今天我是需要做的是通过函数来计算约瑟夫环中的最后那个数是什么。

其实这里不过是需要一个成环的单链表,然后通过循环不断的找到第m个数然后将第m个数删除,将m-1个数的next指向m+1。并不复杂。

SListNode* JosephCycle(SListNode* head, int k)

{

SListNode* tail = head, *cur = head;

if(head == NULL)

return NULL;

 

// 构成环

while (tail->_next)

tail = tail->_next;

tail->_next = head;

 

while (cur->_next != cur)

{

SListNode* next;

int count = k;

while (--count)

cur = cur->_next;

 

next = cur->_next;

cur->_data = next->_data;

cur->_next = next->_next;

 

free(next);

}

 

return cur;

}

 


 

while (tail->_next)

tail = tail->_next;

tail->_next = head;


这里先找到链表的最后一个节点,然后将这个链表变成一个环,其实我感觉这样的话要比传进来一个成环的链表比较好,这样操作起来更方便。

 

 

 

while (cur->_next != cur)

{

SListNode* next;

int count = k;

while (--count)

cur = cur->_next;

 

next = cur->_next;

cur->_data = next->_data;

cur->_next = next->_next;

 

free(next);

}

 

这里while的循环条件就是至少这个链表存在一个元素,如果只有一个元素的话就会退出循环。然后这里要注意的就是,不能直接将你传进来的k进行操作,你需要设定另外一个值来进行操作,不然一次循环结束之后就不能再找到你的k是多少了。

这里删除这个结点很多种的方法,我这里用的是首先用next将你的cur的下一个节点存起来然后将next的值给了cur,实际上就是把以前的数据给覆盖了,以前数据丢失。然后将你现在的这个结点的next指向刚刚next的next,然后把没用的next结点free掉因为这时候next的值已经放在cur中了,这时候的cur实际上就是之前的next。