Data Structure:

...

function reverseLinkedList(head):
    // initialize variables
    prev = null
    curr = head

    // loop through the linked list
    while curr is not null:
        // save the next node
        nextNode = curr.next

        // reverse the current node's pointer
        curr.next = prev

        // move pointers to the next nodes
        prev = curr
        curr = nextNode

    // update the head of the linked list
    head = prev

    // return the reversed linked list
    return head
Copy

see this link to get a better understanding of the problem.

we do it by using linked list:

function josephus(n, k):
    // create a linked list with n nodes
    head = createLinkedList(n)

    // initialize pointers
    curr = head
    prev = null

    // loop through the linked list
    while lengthOfLinkedList(head) > 1:
        // find the kth node
        for i in range(k - 1):
            prev = curr
            curr = curr.next

        // remove the kth node
        if prev is null:
            head = curr.next
        else:
            prev.next = curr.next

        // move to the next node
        curr = curr.next

    // return the remaining node
    return head.value
Copy

we also have a recursive method to solve it

The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e. . (For the more general case , a solution is outlined below.) The solution is expressed recursively. Let denote the position of the survivor when there are initially n people The first time around the circle, all of the even-numbered people die. The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it is as though there were no first time around the circle.

If the initial number of people was even, then the person in position x during the second time around the circle was originally in position (for every choice of x). Let . The person at who will now survive was originally in position . This yields the recurrence

If the initial number of people was odd, then person 1 can be thought of as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc. In this case, the person in position x was originally in position . This yields the recurrence

we can implement this by using a matrix where first row is pointer to before, second row is variable data, third row is pointer to after also we can store free spaces in a external array or a better approach is every time we remove a column we can put the last column in that column so we always have a full side and an empty side for our array that we can use to allocate more nodes.

session 7