python环形单链表的约瑟夫问题详解

题目：

一个环形单链表，从头结点开始向后，指针每移动一个结点，就计数加1，当数到第m个节点时，就把该结点删除，然后继续从下一个节点开始从1计数，循环往复，直到环形单链表中只剩下了一个结点，返回该结点。

这个问题就是著名的约瑟夫问题。

代码：

首先给出环形单链表的数据结构：

class Node(object):
def __init__(self, value, next=0):
 self.value = value
 self.next = next # 指针

class RingLinkedList(object):
# 链表的数据结构
def __init__(self):
 self.head = 0 # 头部

def __getitem__(self, key):
 if self.is_empty():
  print 'Linked list is empty.'
  return
 elif key < 0 or key > self.get_length():
  print 'The given key is wrong.'
  return
 else:
  return self.get_elem(key)

def __setitem__(self, key, value):
 if self.is_empty():
  print 'Linked list is empty.'
  return
 elif key < 0 or key > self.get_length():
  print 'The given key is wrong.'
  return
 else:
  return self.set_elem(key, value)

def init_list(self, data): # 按列表给出 data
 self.head = Node(data[0])
 p = self.head # 指针指向头结点
 for i in data[1:]:
  p.next = Node(i) # 确定指针指向下一个结点
  p = p.next # 指针滑动向下一个位置
 p.next = self.head

def get_length(self):
 p, length = self.head, 0
 while p != 0:
  length += 1
  p = p.next
  if p == self.head:
   break
 return length

def is_empty(self):
 if self.head == 0:
  return True
 else:
  return False

def insert_node(self, index, value):
 length = self.get_length()
 if index < 0 or index > length:
  print 'Can not insert node into the linked list.'
 elif index == 0:
  temp = self.head
  self.head = Node(value, temp)
  p = self.head
  for _ in xrange(0, length):
   p = p.next
  print "p.value", p.value
  p.next = self.head
 elif index == length:
  elem = self.get_elem(length-1)
  elem.next = Node(value)
  elem.next.next = self.head
 else:
  p, post = self.head, self.head
  for i in xrange(index):
   post = p
   p = p.next
  temp = p
  post.next = Node(value, temp)

def delete_node(self, index):
 if index < 0 or index > self.get_length()-1:
  print "Wrong index number to delete any node."
 elif self.is_empty():
  print "No node can be deleted."
 elif index == 0:
  tail = self.get_elem(self.get_length()-1)
  temp = self.head
  self.head = temp.next
  tail.next = self.head
 elif index == self.get_length()-1:
  p = self.head
  for i in xrange(self.get_length()-2):
   p = p.next
  p.next = self.head
 else:
  p = self.head
  for i in xrange(index-1):
   p = p.next
  p.next = p.next.next

def show_linked_list(self): # 打印链表中的所有元素
 if self.is_empty():
  print 'This is an empty linked list.'
 else:
  p, container = self.head, []
  for _ in xrange(self.get_length()-1): #
   container.append(p.value)
   p = p.next
  container.append(p.value)
  print container

def clear_linked_list(self): # 将链表置空
 p = self.head
 for _ in xrange(0, self.get_length()-1):
  post = p
  p = p.next
  del post
 self.head = 0

def get_elem(self, index):
 if self.is_empty():
  print "The linked list is empty. Can not get element."
 elif index < 0 or index > self.get_length()-1:
  print "Wrong index number to get any element."
 else:
  p = self.head
  for _ in xrange(index):
   p = p.next
  return p

def set_elem(self, index, value):
 if self.is_empty():
  print "The linked list is empty. Can not set element."
 elif index < 0 or index > self.get_length()-1:
  print "Wrong index number to set element."
 else:
  p = self.head
  for _ in xrange(index):
   p = p.next
  p.value = value

def get_index(self, value):
 p = self.head
 for i in xrange(self.get_length()):
  if p.value == value:
   return i
  else:
   p = p.next
 return -1

然后给出约瑟夫算法：

def josephus_kill_1(head, m):
 '''
 环形单链表，使用 RingLinkedList 数据结构，约瑟夫问题。
 :param head:给定一个环形单链表的头结点，和第m个节点被杀死
 :return:返回最终剩下的那个结点
 本方法比较笨拙，就是按照规定的路子进行寻找，时间复杂度为o(m*len(ringlinkedlist))
 '''
 if head == 0:
  print "This is an empty ring linked list."
  return head
 if m < 2:
  print "Wrong m number to play this game."
  return head
 p = head
 while p.next != p:
  for _ in xrange(0, m-1):
   post = p
   p = p.next
  #print post.next.value
  post.next = post.next.next
  p = post.next
 return p

分析：

我采用了最原始的方法来解决这个问题，时间复杂度为o(m*len(ringlinkedlist))。
但是实际上，如果确定了链表的长度以及要删除的步长，那么最终剩余的结点一定是固定的，所以这就是一个固定的函数，我们只需要根剧M和N确定索引就可以了，这个函数涉及到了数论，具体我就不细写了。

来源：https://blog.csdn.net/dongrixinyu/article/details/78717547