环形链表，约瑟夫问题，（7）

àì夳堔傛蜴生んèń 2022-06-09 11:22 198阅读 0赞

一个经典的环形链表问题，有1,2，3，，，，n这些数字排成一个圆圈，从1开始每次删除第m个数字，求出这个圆圈中最后的数字。当然也可以说先从数字k开始，数到m删除这个数字，然后就从1开始，数到m删除这个数字，原理是一样。

这里是从1开始，数到m删除这个数字。

其实一个单向非循环链表也是可以模拟这个应用的，就是当指针指到最后一个节点时，让他转到头结点继续遍历。

下面的实例是环形链表，尾节点的下一个节点是头结点，已经指好了。

#include <iostream>
    #include "ListCommon.h"
    
    using namespace std;
    
    ListNode* lastRemainListNode(ListNode* pHead, int move){
    	if(pHead == NULL || move <1){
    		return NULL;
    	}

//只有一个节点的情况 pHead->m_pNext == pHead

if(pHead->m_pNext == pHead){
    		cout << "only one node!" <<endl;
    		return pHead;
    	}
    
    	ListNode* pNode = pHead;
    	ListNode* pLast = pHead;
    	//让pLast指向pNode的前一个节点，实际也是要删除的那个节点的前一个节点
    	while(pLast->m_pNext != pHead){
    		pLast = pLast->m_pNext;
    		
    	}
    	cout<<"pLast="<<pLast->m_nValue<<endl;
    	int count =0;

//仅剩一个节点时循环终止 pNode == pLast

while(pNode != pLast){
    		cout<<"count="<<count<<",move="<<move<<",pNode="<<pNode->m_nValue<<",pLast="<<pLast->m_nValue<<endl;
    		if(++count == move){
    		//到达计数值m，删除pNode，删除前先把指针指好，pLast始终指向pNode的前一个节点，所以pLast的next指向pNode的next就等于把pNode删除了。
    			pLast->m_pNext = pNode->m_pNext;
    			delete pNode;
    			pNode = NULL;			
    			count = 0;
    		}else{
    		//继续遍历
    			pLast = pLast->m_pNext;
    		}
    		//使pLast指向pNode的前一个节点
    		pNode = pLast->m_pNext;		
    	}
    	return pNode;
    }
    
    int main(int argc, char* argv[]){
    	ListNode* pNode1 = CreateListNode(1);
    	ListNode* pNode2 = CreateListNode(2);
    	ListNode* pNode3 = CreateListNode(3);
    	ListNode* pNode4 = CreateListNode(4);
    	ListNode* pNode5 = CreateListNode(5);
            ConnectListNodes(pNode1,pNode2);
            ConnectListNodes(pNode2,pNode3);
            ConnectListNodes(pNode3,pNode4);
            ConnectListNodes(pNode4,pNode5);
    	ConnectListNodes(pNode5,pNode1);//尾节点5指向头结点1
    	
    	PrintList(pNode1);//打印整个链表，
    	PrintListNode(pNode5->m_pNext);//打印输出尾节点的下一个节点，表明这是一个环形链表
    	ListNode* pNode = lastRemainListNode(pNode1,3);//处理删除
    	PrintListNode(pNode);//最后剩余的节点数值
    	return 0;
    }

测试结果：

粘贴了多个测试结果，其中move就是m的值：

PC:~/algorithm$ g++ ListCommon.cpp CircularList.cpp -o CircularList  
PC:~/algorithm$ ./CircularList  
print list begin ---  
1  
2  
3  
4  
5  
print list end  
The value of node is 1  
pLast=5,move=3  
count=0,move=3,pNode=1,pLast=5  
count=1,move=3,pNode=2,pLast=1  
count=2,move=3,pNode=3,pLast=2  
count=0,move=3,pNode=4,pLast=2  
count=1,move=3,pNode=5,pLast=4  
count=2,move=3,pNode=1,pLast=5  
count=0,move=3,pNode=2,pLast=5  
count=1,move=3,pNode=4,pLast=2  
count=2,move=3,pNode=5,pLast=4  
count=0,move=3,pNode=2,pLast=4  
count=1,move=3,pNode=4,pLast=2  
count=2,move=3,pNode=2,pLast=4  
The value of node is 4

数到1就删除，剩下的就是5，

PC:~/algorithm$ g++ ListCommon.cpp CircularList.cpp -o CircularList  
linjw@linjw-PC:~/algorithm$ ./CircularList  
print list begin ---  
1  
2  
3  
4  
5  
print list end  
The value of node is 1  
pLast=5,move=1  
count=0,move=1,pNode=1,pLast=5  
count=0,move=1,pNode=2,pLast=5  
count=0,move=1,pNode=3,pLast=5  
count=0,move=1,pNode=4,pLast=5  
The value of node is 5  
  
数到2删除，剩下的就是3：

PC:~/algorithm$ g++ ListCommon.cpp CircularList.cpp -o CircularList  
linjw@linjw-PC:~/algorithm$ ./CircularList  
print list begin ---  
1  
2  
3  
4  
5  
print list end  
The value of node is 1  
pLast=5,move=2  
count=0,move=2,pNode=1,pLast=5  
count=1,move=2,pNode=2,pLast=1  
count=0,move=2,pNode=3,pLast=1  
count=1,move=2,pNode=4,pLast=3  
count=0,move=2,pNode=5,pLast=3  
count=1,move=2,pNode=1,pLast=5  
count=0,move=2,pNode=3,pLast=5  
count=1,move=2,pNode=5,pLast=3  
The value of node is 3

这个问题还有一个递归算法，先假定有0,1,2，。。。n-1，这个n个数的环，

我们用f(n,m)表示最后剩余的那个数的编号，

第一轮循环，出列的那个编号肯定是m-1，当m<n时可以这么表示，考虑到m可能大于n，所以表示为(m-1)%n，

![Center][]

第一轮出列的是m-1，第二轮循环开始的位置就是m，

根据这个映射，m对应0，m+1对应1，…，m-1对应了n-1,这样第二轮实际就是总共n-1个数，从0开始计数的环，所以第二轮剩余的那个数的编号表示为f(n-1,m)，

那么f(n,m)跟f(n-1,m)肯定是对应的，只是第二轮的起点实际是m，而不是0，

所以有f(n,m)=(f(n-1,m) +m ) % n。

根据这个递推，直到f(1)= 0，然后依次回溯f(2),f(3),…,f(n)

比如n=3，m=2：

f(3,2) =(f(2,2)+2)%3;

f(2,2) =(f(1,2)+2)%2;

f(1,2) =0;

所以有：f(2,2)=(0+2)%2 =0;

f(3,2)=(0+2)%3=2;最后保留的就是2。

代码实例：

#include <iostream>
    #include "ListCommon.h"
    
    using namespace std;
    int josephusRecursion(int length, int count){
    	if(length <1 || count < 1){
    		return -1;
    	}
    	if(length ==1){
    		return 0;
    	}
    	return (josephusRecursion(length-1,count) + count)%length;
    }
    
    int main(int argc, char* argv[]){
    	int remain_1 = josephusRecursion(5,3);
    	cout << "josephusRecursion ,length =5,count=3,ramain =" <<remain_1<<endl;
    	int remain_2 = josephusRecursion(3,2);
    	cout << "josephusRecursion ,length =5,count=2,ramain =" <<remain_2<<endl;
    	return 0;
    }

测试结果：

PC:~/algorithm$ g++ ListCommon.cpp CircularList.cpp -o CircularList  
PC:~/algorithm$ ./CircularList  
josephusRecursion ,length =5,count=3,ramain =3  
josephusRecursion ,length =5,count=2,ramain =2

[Center]: /images/20220609/36dfcb2836b94f3ca7d04cdb4deae163.png