Josephus环的问题单链表python

Josephus环问题是计算机科学中经典的一个算法问题，它通常涉及一个循环数组（在这里可以理解为单链表），在这个环上每隔k步删除一个节点，然后让剩下的最后一个节点继续行走，直到环为空。这个问题是以罗马统帅约瑟夫斯命名的，他命令士兵们排成一圈，从某个指定位置开始报数，每到特定数值就被处决。

在Python中解决Josephus环问题，你可以按照以下步骤：

1. 首先，需要将单链表转换为一个环形结构，因为原问题假设了环的存在。
2. 定义一个函数`next_kth_node`，接受链表头节点和步长k作为参数。这个函数会遍历链表，每次跳过k-1个节点，直到找到第k个节点并返回它。
3. 当链表只剩下一个节点时，说明已经找到了最后的存活者，它是新的环的头节点。
4. 如果链表还有多个节点，重复执行`next_kth_node`，直到链表为空。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def josephus_linked_list(head, k):
    if not head or not head.next:
        return None  # 环只有一个节点或者空链表，直接返回

    slow = head  # 慢指针，每次走1步
    fast = head  # 快指针，每次走k步
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next  # 跳过k-1步

    # 找到k个节点后的第一个节点，即新环的起点
    new_head = slow.next
    slow.next = None  # 断开原链表形成环

    # 继续执行Josephus规则
    return josephus_linked_list(new_head, k)

# 示例
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
k = 2
result = josephus_linked_list(head, k)