CareerCup

this question is known as the "Josephus problem" ... search on wikipedia

int josephus(int n, int k)
{
    printf("LL Size: %d, OffSet: %d\n", n, k);
    if (n == 1)
        return 1;
    else /* The position returned by josephus(n - 1, k) is adjusted because the
            recursive call josephus(n - 1, k) considers the original position k%n + 1 as position 1 */
        return (josephus(n - 1, k) + k-1) % n + 1;
}

As per given direction : I think it is the best one!
"There is an O(n) solution based on mathematics, the iterative equation is the following:

f[1]=0;

f[i]=(f[i-1]+k)%i; (i>1)

and f[n]+1 is the your final answer."

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int value;
  struct node* next;
}node;

node* getNode (int val) {
  node *element ;
  element = (node *) malloc (sizeof(node)) ;
  element->value = val ;
  element->next = NULL ;
  return element ;
}

node* addNode (node* head, node *element) {
  node *temp = head ;
  if ( head == NULL ) {
    head = element ;
    head->next = head ;
    return head ;
  }
  while (temp->next != head)
    temp = temp->next ;
  temp->next = element ;
  element->next = head ;
  return head ;
}


void printList(node *head) {
  node *temp = head ;
  if (head) {
    while ( temp->next != head ) {
      printf ( "%d ", temp->value ) ;
      temp = temp->next ;
    }
    printf ( "%d", temp->value ) ;
  }
}

node* getKthNode (node *list, int k, int size) {
  int oldVal = 0, i, newVal ;

  node *temp = NULL, *element ;
  for ( i = 2 ; i <= size ; i ++ ) {
    newVal = (oldVal + k) % i ;
    oldVal = newVal ;
  }
  newVal ++ ;

  temp = list ;
  if ( size == 1 )
    return list ;

  for ( i = 1 ; i < newVal; i++ ) {
    list = list->next ;
    free (temp) ;
    temp = list ;
  }
  element = list ;
  element->next = NULL ;
  list = list->next ;

  for ( i = newVal+1 ; i < size ; i++ ) {
    list = list->next ;
    free (temp) ;
    list = list->next ;
  }
  free (list) ;
  return element ;
}

int main() {
  node *head = NULL, *temp ;
  int size, i, val, k;
  printf ( "\nEnter the sie :\t" ) ;
  scanf ( "%d", &size ) ;

  for ( i = 0 ; i < size ; i ++ ) {
    printf ( "\nEnter the value :\t" ) ;
    scanf ( "%d", &val ) ;
    head = addNode (head, getNode(val)) ;
  }
  printf ( "\n" );
  printList(head);
  printf ( "\nEnter the k :\t" ) ;
  scanf ( "%d", &k ) ;

  temp = getKthNode (head, k, size) ;
  if ( temp != NULL )
    printf ( "\nLast node :\t%d\n", temp->value ) ;
  return 0;
}

This is a tricky problem, i'm trying to figure out how to make it O(n). For instance, say we have n = 10 nodes and k = 100,000. Before we delete our first element, we would have traveled 100,000 times in a linked list. We would do this n-1 times = (n-1)*k = O(n*k). Assuming k is big, and not a "constant", this is not O(n).

Another solution is finding the index of the node to destroy via modular arithmetic and then go to that node to destroy it. Let n = 10 and k = 14. Assuming nodes numbered 0 to 9, and we start at 0, we have 10 % 14 = 4. So 0 + 4 = 4. Go to node 4 and delete it. We're not "starting" where node 4 was. Next, we now have n = 9 nodes, 9 % 14 = 5. 4 + 5 = node 9. Repeat this n-1 times until we have n nodes left. You can test this on paper with 10 labeled nodes from 0 to 9. We first delete node 4 then if we go around 14 more times we'll arive at node 9, which was 4 + 5. Unfortunately, this is (n-1)*n = O(n^2). This is better than O(n*k) if k is > n, but still not O(n).

Should I be assuming k is a constant and not another variable to the function? I mean, if the function is getLastNode(Nodes n, int k) then the input is not just n, k may change as well. If k was always 5 for example, then we could say O(n*5) = O(n).

Hi,

There is an O(n) solution based on mathematics, the iterative equation is the following:

f[1]=0;

f[i]=(f[i-1]+k)%i; (i>1)

and f[n]+1 is the your final answer.

Then you just need to follow the linked list from the head till you reach the f[n]+1 (starting from 1, not 0) element.

For the above example:
f[1] = 0
f[2] = (0+3)%2 = 1
f[3] = (1+3)%3 = 1
f[4] = (1+3)%4 = 0
f[5] = (0+3)%5 = 3.

So the final answer is the 4th element in the list.

Code :

int delete_kth_node( node *head, int n, int k)
{
	node *current_node = head;

	while(n > 1)
	{
		int dist = (k % n)-1;
		node *temp = NULL;

		if(dist == -1)
			dist = n-1;
		
		while(dist > 0)
		{
			current_node = current_node->next;
			dist--;
		}

		temp = current_node->next;
		current_node->next = temp->next;

		if(temp == head)
			head = temp->next;

		free(temp);
		temp = NULL;
		n--;

		printf("\n");
		print_list(head, n);
		
		current_node = current_node->next;
	}

	return head->val;
}

int delet_kh_node( node*& head, int k)
{
if( head )
{
if(head->next)
{
while(head->next!=head)
{
for(int i=1; i<k-1; i++ )

head=head->next;

node *t=head->next;

head->next=t->next;

head=head->next;

delete t;
}
}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QCircularList {
    private static final int K_ELEMENT = 3 - 1;

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        int idx = K_ELEMENT;
        while (list.size() != 1) {
            System.out.println("removed element at index: " + idx);
            list.remove(idx);
            printList(list);
            idx = nextRemovalIndex(idx, list);
        }

    }

    private static int nextRemovalIndex(int idx, ArrayList<Integer> list) {
        int loop = 0;
        do {
            idx++;
            idx = idx % list.size();
            loop++;
        } while (loop < K_ELEMENT);
        return idx;
    }

    private static void printList(List<Integer> asList) {
        int i = 0;
        for (int a : asList) {
            System.out.println("a[" + i + "]: " + a);
            i++;
        }
        System.out.println("---------------------------");
    }

}

sorry I rush the answer, no need the method that loops to calculate the next index

public class QCircularList {
    private static final int K_ELEMENT = 3 - 1;

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        int idx = K_ELEMENT;
        while (list.size() != 1) {
            System.out.println("removed element at index: " + idx);
            list.remove(idx);
            printList(list);
            idx = (idx+K_ELEMENT) % list.size();
        }
    }

    private static void printList(List<Integer> asList) {
        int i = 0;
        for (int a : asList) {
            System.out.println("a[" + i + "]: " + a);
            i++;
        }
        System.out.println("---------------------------");
    }
}

void delete_node(struct circular **node, int pos)
{
struct circular *q, *p, *temp;
int i=0,j;
q = *node;
if((*node) == NULL)
printf("Link List is empty\n");
else if((*node)->next == NULL)
printf("final node is %d\n",(*node)->data);
else
{
q=(*node);
while(q->next != q)
{
for(i=1;i<pos;i++)
{
q = q->next;
}
if(q && q->next && (q->next != q))
{
temp = q->next;
q->next = q->next->next;
if(temp)
delete temp;
}
p = q;
while(p->next != q)
{
p = p->next ;
printf("%d-->",p->data);
}
p=p->next;
printf("%d\n\n",p->data);
}
}
}

#include <stdio.h>

struct node{
int info;
struct node * next;
};

struct node * head;

void addBeg(int x){
struct node * temp = (struct node *)malloc(sizeof(struct node));
temp->info = x;
temp->next = head;
head=temp;
}

void display(){
struct node * temp = head;
while(temp!=NULL){
printf("%d\n",temp->info);
temp = temp->next;
}
}

void makeCircular(){
struct node * temp = head;
while(temp!=NULL && temp->next!=NULL){
temp=temp->next;
}
temp->next = head;
}

void deleteK(int pos){
struct node * temp1;
int i;
for(i=1;i<pos-1;i++){
head = head->next;
}
temp1= head->next;
head->next = temp1->next;
free(temp1);
head = head->next;
if(head->next!=head)
deleteK(pos);
else
printf("Last Element %d",head->info);
}

int main(){
addBeg(5);
addBeg(4);
addBeg(3);
addBeg(2);
addBeg(1);
makeCircular();
deleteK(5);
return 0;
}

private static void delete(node first, int i) {
		// TODO Auto-generated method stub
		node save = first;
		node startfrom = first;
		node prev = null;
		int count =1;
		while(count<i){
			if(first.next==first){
				System.out.println( "" +first.data + first.next.data + first.next.next.data + first.next.next.next.data + first.next.next.next.next.data);
				return;
			}
			else{
				prev = first;
				first = first.next;
				count++;
			}
			
		}
		prev.next = first.next;
		startfrom = first.next;
		first = null;
		first = save;
		System.out.println( "" +first.data + first.next.data + first.next.next.data + first.next.next.next.data + first.next.next.next.next.data);
		delete(startfrom,i);
		
	}

#include<stdio.h>
typedef struct node
{
  int value;
  struct node* next;
}Node;
typedef Node* NodePtr;
NodePtr AddToList(NodePtr list,int data);
void PrintList(NodePtr list);
int Length(NodePtr list);
int ValueAt(NodePtr list,int pos);
int main()
{
   NodePtr List=NULL;
   //int a[]={1,2,3,4,5,6};
   int i=0,count,data,k;
   scanf("%d",&k);
   scanf("%d",&count);
   for(i=0;i<count;i++)
   {
     scanf("%d",&data);
	 List=AddToList(List,data);
	 //PrintList(List);
   }
   PrintList(List);
   int n=Length(List);
   int *f=(int *)malloc(sizeof(int)*n);
   //printf("\nLength= %d",Length(List));
   f[0]=0;
   for(i=1;i<n;i++)
   {
      f[i]=(f[i-1]+k)%(i+1);
   }
   printf("\n Node to be deleted is %dth node and its value is %d",f[n-1]+1,ValueAt(List,f[n-1]+1)); 
}

NodePtr AddToList(NodePtr list,int data)
{
   NodePtr travel=NULL;
   NodePtr newNode;
   newNode=(NodePtr)malloc(sizeof(Node));
   newNode->value=data;
   newNode->next=list;
   if(list==NULL)
   {
      newNode->next=newNode;
      list=newNode;
	  return list;
   }
   travel=list;
   while(travel->next!=list)
   {
      travel=travel->next;
   }
   travel->next=newNode;
   return list;
}

void PrintList(NodePtr list)
{
   NodePtr travel=list;
   printf("\n");
   while(travel->next!=list)
   {
     printf("%d ->",travel->value);
	 travel=travel->next;
   }
   printf("%d -->",travel->value);
   printf("%d",travel->next->value);
}

int Length(NodePtr list)
{
  int count=0;
  NodePtr travel=list;
   while(travel->next!=list)
   {
     count++;
	 travel=travel->next;
   }
   count++;
   return count;
}

int ValueAt(NodePtr list,int pos)
{
   int i=1;
   NodePtr travel=list;
   while(travel->next!=list)
   {
      if(i==pos)
	   return travel->value;
	  i++;
	  travel=travel->next;
   }   
   if(i==pos)
    return travel->value;
}

import java.util.LinkedList;

public class KRemoveFromCircularLinkedList<E> {

    public static <E> E kRemove(LinkedList<E> list, int k) {
        /*
            size    k-condition         result
            0                           IllegalArgumentException
            1                           return list[1]
            n       k in [0..n-1]       return list[1]
         */

        if (list.size() == 0)
            throw new IllegalArgumentException();

        if (list.size() == 1)
            return list.element();

        if (k < 0 || k >= list.size())
            throw new IndexOutOfBoundsException();

        int start = 0;
        while (list.size() > 1) {
            int elToDelete = (start + k - 1) % list.size();
            list.remove(elToDelete);
            start = elToDelete % list.size();
        }
        return list.element();
    }
}

link(node *head,int n)
start from the head while(node->next!=head&&count<k)
{*p=node;
node=node->next;count++;}
if(count==k&&node->next!=head)
{t=node->next;
node->next=t->next;
t->next=NULL;
link(node *head,int n);}
else if(count==k)
{
node->next=head;
}

public static int getSurviveNode(LinkedListNode head,int times){
if(head.next==head){
return head.data;
}
LinkedListNode current=head.next;
while(current.next!=head){
current=current.next;
}
LinkedListNode pervious=current;
current=head;
int killtimes=1;
while(current.next!=current){
if(killtimes==times){
pervious.next=current.next;
current.next=null;
current=pervious.next;
killtimes=1;
continue;
}
else{
pervious=current;
current=current.next;
killtimes++;
}
}
return current.data;
}

all codes looks very clustered. i have simple solution.
node *cur=start;
while(cur->next!=cur)
{
node *temp=cur->next->next;
cur->next->next=temp->next; // deleting the link
cur=temp->next // for next deltion;
delete(temp);

}

namespace
{
    template <typename T>
    struct Node
    {
        T value;
        int next;
        Node() : next(-1) {}
    };

    template <typename T>
    class Ring
    {
        int _capacity; // Capacity of Ring (initially)
        int _size; // Valid Node Count
        int _current; // Current node
        Node<T>* _nodes; // Collection of Nodes

    public:
        Ring(int cap) : _capacity(cap), _size(0), _nodes(NULL), _current(-1)
        {
            _nodes = new Node<T>[cap];
            
            for(int aa = 0; aa < cap; ++aa)
                _nodes[aa].next = (aa+1)%cap;

            _size = cap;
            _current = 0;
        }

        ~Ring()
        {
            if(_nodes) { delete [] _nodes; _nodes = NULL; }
        }

        int Size() const { return _size; }

        int DeleteAndMove(int step)
        {
            if(_size < 1) throw "The ring is empty";

            //
            // Move prior to deleting node
            //
            for(int aa = 0; aa < step - 1; ++aa)
                _current = _nodes[_current].next;

            int toDelete = _nodes[_current].next;
            printf("deleting %d ..\n", toDelete);
            _nodes[_current].next = _nodes[toDelete].next;
            _nodes[toDelete].next = -1;
            _current = _nodes[_current].next;
            --_size;

            return _size;
        }
    };

    void DeleteTest(int size, int space)
    {
        Ring<int>* ring = new Ring<int>(size);

        try
        {
            while(ring->Size() != 1)
            {
                ring->DeleteAndMove(space);
            }
        }
        catch(const char* msg)
        {
            fprintf(stderr, "%s\n", msg);
        }
    }
}

void SK::SampleQuestions::KthNodeRemoval()
{
    DeleteTest(101, 7);
}

Above will leak memory (forgot to delete 'ring'). Spoiled from smart-pointers...

I guess double link list will work. The total traversal will be O(N). We'll start following the next pointer with count, once find 'k' delete the node. In case nxt is null we'll follow previous to get (k-count) and keep on doing unless get prev==NULL and ther revert to next and so on.

A nxn array of pointers to the given circular linked list.
If I understand the question correctly, the problem is to design a data structure that is efficient enough to delete all elements in linked list for any given value of k in O(n) time. In other words for any value of K, this data structure that you design should take O(n) time to delete all the elements.
Note: The deletion should follow the pattern specified in the question.


In order to achieve this, we have to cache the deletion sequence for each value of K.
A simple nxn dimension array would suffice. Each row would contain the deletion sequence for a given value of K.
Example:
a[n][n]
The deletion sequence for K=1 could be cached in the 0th row of the array, a[0][0] to a[0][n] - n pointers the the 1st successor of every element starting from the head.
For k=2 the sequence would be stored in the 1st row of the array, a[1][0] to a[1][n].

In general, for any value of K, we just need to delete the all nodes in the row k-1 sequentially, a[k-1][0] to a[k-1][n]. - this will achieve O(n) time.

How about a circular array?
Array where after array.length -1 position we come back to position 0.
Basically using modulo operation.
For elements which are removed in those cells in the array we can have some pre-defined indentifier number to indicate empty cell.
Removal for single element will be O(1) since we can find the exact index which has to be free.
So for n elements the removal will be O(n).
Please provide suggestions on this solution.

I also don't see any way to do the whole thing in O(n). I hope the person who posted this question didn't mean O(n) for each iteration, hence O(n^2) total...

I may be missing something here but couldn't you use an array?

To remove every kth item we increment by the index by k and remove that item. We just need to check to see if our index is greater than array.length() -1, and if it is simply take that away from the index to maintain a circular structure.

Then if we encounter an item that has been removed (either by noticing it is null, or by having a special static 'removed' item to swap with if the array items may be null) we simply increment the index by 1. (Because the next item should be in this index, it's just that rebuilding an array is expensive). That should only happen if the array length is evenly divided by k.

Correct.

This is josephus problem..

This can be done either using recursion

int josephus(int n, int k)
{
  if (n == 1)
    return 1;
  else
    /* The position returned by josephus(n - 1, k) is adjusted because the
       recursive call josephus(n - 1, k) considers the original position 
       k%n + 1 as position 1 */
    return (josephus(n - 1, k) + k-1) % n + 1;
}

or by iteration,

f[1] = 0
f[i] = (f[i-1]+k)%i

final result would be

f[n]+1

void precomp() {
    int i;
    val[1] = 0;
    for (i = 2; i < MAX; i++)
        val[i] = (val[i-1]+k)%i;
}

C Code:

First the header file to create double circular linked list:

#include <stdio.h>
#include <stdlib.h>

#ifndef __DATASTRUCTURE
#define __DATASTRUCTURE

typedef struct node
{
	int id;
	struct node *next;
	struct node *prev;
} Node;

Node* createNextNode(int id, Node *callingNode)
{
	Node *temp = (Node*)malloc(sizeof(Node));
	
	temp->id = id;
	
	if (callingNode != NULL)
	{
		temp->next = callingNode->next;
		temp->prev = callingNode;
		
		callingNode->next = temp;
		
		temp->next->prev = temp;
	}
	else
	{
		temp->next = temp;
		temp->prev = temp;
	}
	
	return temp;
}

void deleteNode(Node *unwantedNode)
{
	unwantedNode->prev->next = unwantedNode->next;
	unwantedNode->next->prev = unwantedNode->prev;
	
	free(unwantedNode);
}

void printNodesForward(Node *startNode)
{
	Node *temp = startNode;
	
	do
	{
		printf("%d\t", temp->id);
		temp = temp->next;
	}while(temp != startNode);
	
	printf("\n");
}

void printNodesBackward(Node *startNode)
{
	Node *temp = startNode;
	
	do
	{
		printf("%d\t", temp->id);
		temp = temp->prev;
	}while(temp != startNode);
	
	printf("\n");
}

#endif

Then the actual code to remove every kth node in o(n) time. Note that the traversal to reach the nth node takes o(n) time.

#include "dataStructure.h"

int main(int argc, char **argv)
{
	if (argc != 3)
	{
		printf("Usage: ./a.out <totalNodes> <jumpBy>\n");
		return 1;
	}
	
	int totalNodes = atoi(argv[1]);
	int jumpBy = atoi(argv[2]) % totalNodes;
	
	Node *callingNode = createNextNode(1, NULL);
	Node *startNode = callingNode;
	
	int i = 2;
	
	do
	{
		callingNode = createNextNode(i, callingNode);
		
		i++;
	}while(i != totalNodes+1);
	
	while(totalNodes != 1)
	{
		for (i = 1; i != jumpBy; i++)
		{
			startNode = startNode->next;
		}
		
		Node *unwantedNode = startNode;
		startNode = startNode->next;
		deleteNode(unwantedNode);
		
		printNodesForward(startNode);
		
		totalNodes--;
	}
	
	return 0;
}

General approach for this problem is to use circular linkedlist.

Just using a plain circular linked list will give O(kn) complexity. if k=n, that would lead to O(n^2) complexity. Something like this -

struct node *r = root;
struct node *todelete = NULL;
for (int i=n; i>0; --i)
{
    for (int j=0; j < k; j++)
        r = r->next;

    todelete = r->next;
    r->next = r->next->next;
    free(todelete);
}

This is due to the traversal we do every loop to reach the kth node. So finding a way to remove this traversal each time.

Use a array which has random access. Create array of length n and store all n elements in them. At each position of the array store the data. start the deletion process. in each loop jump to that kth location & delete that data. Incase we goto a location with no data (it might have already been deleted), then shift one place to right & see if there is data there. And so on... This approach is somewhat like "openaddressing hashtable collision resolution approach".

Time O(n), space O(2n)

Data Structure

Node is a class with 2 instance variable int X and int Y as coordinates.
Circle is a class with a instance variable NodesLinkedList. Connect the last node to the first Node in the linked list to make it circular Linked List.
To removing the K th Node from NodesLinkedList add a Method removeNode(Int k)

For Ease of understanding
Assume NodesLinkedList has 100 Nodes. 100 th Node is connected to 1 st Node.
Node to be deleted K th Node is 5.
First time 5 th node is deleted and 95 nodes remain. This goes on till we have last 4 nodes.
Since this is circular. It goes on until we have 1 node.

The question asks you to design a O(n) time complexity. Is it possible that we use basic array implementation and after every deletion we make a fresh copy of array of (current_size-1)? After first iteration new array is of size n-1 and we perform k % (n-1) to find next index to be deleted.

So, as many said before, this problem can be easily implemented using a Circular Double Linked List, and guaranteeing a O(n) complexity. Specifically, the complexity of this implementation will be O(k*n), and because k is a constant, O(k*n)=O(n). Here's my C++ implementation. I think it's quite simple to understand:

struct Node
{
	Node* next;
	int v;
	Node* prev;
};

Node* GetLastNode(Node* node, int k)
{
	Node * tmp = node;

	while(tmp!= NULL)
	{
		for(int i = 0; i<k; i++)
			tmp = tmp->next;

		//Remove tmp node
		Node* to_remove = tmp;
		tmp->prev->next = tmp->next;
		tmp->next->prev = tmp->prev;

		//Update the Node pointer
		tmp = tmp->prev;

		//Check if we reached the last element
		if(tmp==tmp->prev) 
			break;

		delete to_remove;
	}

	return tmp;
}

Note: This implementation can run a little faster if we knew in advance the size of the circular list. Thus, instead of running the "for" loop for k iteration, we can run it in k%n iterations. Of course, in each of the While iteration, we must update the value of "n".

There is also an elegant solution using a Single Linked List. In this case, whenever we want to remove a Node A from the list, we simply copy to the node A the full content of its A->next (pointers and value) and then delete the A->next.

Algorithm is based on Josephus_problem#The_general_case on wikipedia. Time complexity is O(n). The code in C:

#include <stdio.h>
#include <assert.h>

struct Node {
  int val;
  Node* next;
  Node(int val_, Node* next_ = NULL) : 
    val(val_), next(next_) {}
};

int josephus(int n, int k)
{
  int f = 0;
  for (int i = 2; i <= n; i++)
    f = (f + k) % i;
  return f;
}

int len(Node* head)
{
  if (head == NULL) return 0;
  int n = 0;
  Node* q = head;
  do {
    q = q->next;
    n++;
  } while (q != head);
  return n;
}

Node* kill_kth(Node* head, int k)
{
  int n = len(head);
  if (n == 0) return NULL;
  int idx = josephus(n, k);
  printf("idx: %d\n", idx);
  for (int i = 0; i < idx; i++)
    head = head->next;
  return head;
}

Node* list_5_nodes()
{
  Node* node5 = new Node(5);
  Node* node4 = new Node(4, node5);
  Node* node3 = new Node(3, node4);
  Node* node2 = new Node(2, node3);
  Node* node1 = new Node(1, node2);
  node5->next = node1;
  return node1;
}

void test_josephus()
{
  assert(josephus(5, 3) == 3);
  assert(josephus(1, 3) == 0);
}

void test_len()
{
  assert(len(list_5_nodes()) == 5);
}

void test_kill_kth()
{
  Node* head = list_5_nodes();
  Node* only = kill_kth(head, 3);
  printf("%d\n", only->val);
}

int main(int argc, const char *argv[]) 
{
  test_josephus();  
  test_len();
  test_kill_kth();
  return 0;
}

You can arrange the nodes as the distance from their center. What I have done here is defined a simple list, and each element of list is a node that describes the distance from the center. Then from that list I retrieve an element randomly and delete it. I do that until there is one element left.

I could have also done it sequentially i.e delete node 1, node 2.... node n-1

Or I could have made a function to delete the user-specified node until one last element is left.

import random

nodes = list()

for i in range(0, 5):
    n = input("Enter distance from circle: ")
    n = int(n)
    nodes.append(n)

def pickRandom(start, end):
    return random.randint(start, end)

i = len(nodes) - 1
while (i != 0):
    print(nodes)
    del(nodes[pickRandom(0, i)])
    i = i-1

print(nodes)

A circular linked list might be the solution.

This can be done with the help of doubly circular linked list where we can have track of both the previous and next pointers and at last we can add and remove the element in O(n) time