[guzumba15]

Hi everyone! Im am building a Josephus game using Link List that ask the user for the amount of players and the number of passes of the "Hot Potato".

Below is how the the hot potato should be passing and deletion should work:

N people, numbered 1 to N, are sitting in a circle. Person 1 picks up a hot potato and passes it to person 2, who passes it to person 3, and so on. After M passes, the person holding the hot potato is eliminated, the circle closes ranks and the play continues by having the person sitting after the eliminated person pick up the potato and resuming the pass (picking up the potato does not count as one of the M passes). The last person remaining wins the game.

I have got my code this far but now im stuck with the deletion part. If you look at the bottom of the code you will find where I am trying to perform the passes and deletions. Can you guys and gals look and give me something please!?

Thanks everyone!
Andrew

import java.util.Scanner;

class Link
{
   public int iData;
   public Link next;
// -------------------------------------------------------------
   public Link(int id, Link dd) 
   {
      iData = id;
      next = dd;
   }
// -------------------------------------------------------------
   public void displayLink()     
   {
      System.out.print(iData + " ");
   }
}  // end class Link
////////////////////////////////////////////////////////////////
class LinkList
{
   public Link first = null;
	public Link last  = null;

   public LinkList()              
   {
   	first = null;               
   }
	
   public void insert(int id)
   {                           
      Link newLink = new Link( id, null );
      
		newLink.next = first;       
      first = newLink;            
   }

   public Link find(int key)      
   {                           
      Link current = first;              
      while(current.iData != key)        
         {
         if(current.next == null)        
            return null;                 
         else                            
            current = current.next;      
         }
      return current;                   
   }

   public Link delete(int key)    
   {                           
      Link current = first;              
      Link previous = first;
      while(current.iData != key)
         {
         if(current.next == null)
            return null;                
         else
            {
            previous = current;          
            current = current.next;
            }
         }                              
      if(current == first)              
         first = first.next;            
      else                             
         previous.next = current.next;   
      return current;
   }
		
   public void displayList()      
   {
      System.out.print("Players left: ");
      Link current = first;       
      while(current != null)      
         {
         current.displayLink();   
         current = current.next;  
         }
      System.out.println("");
      }
   }  // end class LinkList
////////////////////////////////////////////////////////////////

public class LinkedList
{
   public static void main(String[] args)
      {
	   new LinkedList( );
      }
	public LinkedList( )
        {
	              // instantiate Scanner object
                      Scanner input = new Scanner( System.in );
		      LinkList theList = new LinkList();  
		      int min = 1;
		      int top = 0;
		      int current;
		      int players;
		      int passes;
		      // input number of players and passes
		      System.out.print( "Enter number of players: " );
			players = input.nextInt( );
		      top = players;
		      System.out.print( "Enter number of passes: " );
			passes = input.nextInt( );
		      while ( min <= top )
		      {
			theList.insert(top);
			top--;
		      }  // end while
				
				System.out.println( "Number of players is " + players );
				System.out.println( "Number of passes is " + passes );            
				current = passes+1;
				while ( players >= min)
				{
					theList.displayList();
					Link d = theList.delete(current);
					if( d != null )
		                        System.out.println("Player " + d.iData + " is out!");
					current = d.iData + (passes+1);
					if( current > players )
					current = d.iData + (passes+1) - players;					
					players--;
				}		           
	} 
} // end class LinkedList

[macosxnerd101]

Your delete() method works fine. You are just trying to remove numbers that don't exist in the List. See current = passes+1; and while ( players > min). If current >= players, you will get a NullPointerException. You should look into using a Circularly Linked List, not just a Singly Linked List. So the Tail node should point back to the Head node.

[guzumba15]

Hi everyone! I have built a link list game base off Josephus. I have the game working perfect except for the print out of players remaining. Its printing infinite and I cant see why?

I have made a comment in my playGame( ) method that you must delete to see my issue. If you leave the comment it works perfect except for the print of remaining players.

Thanks for the help everyone!

// File: LinkedLists.java

   import java.util.Scanner;

   class Link
   {
      public int data;
      public Link next;
   
      public Link( int d, Link n )
      {
         data = d;
         next = n;
      }
      public Link( int d )
      {
         this( d, null );
      }
   }  // end class Link

   public class LinkedLists
   {
      int players, passes;
      Link first = null;
      Link last  = null;
      int length = 0;
   
      public static void main( String [] args )
      {
         new LinkedLists( );
      }
   
      public LinkedLists( )
      {
         inputList( );
         playGame( );
      }  // end main
    
      public void inputList( )
      {
      // instantiate Scanner object
         Scanner input = new Scanner( System.in );
         System.out.print( "Enter number of players: " );
         players = input.nextInt( );
         System.out.print( "Enter number of passes: " );
         passes = input.nextInt( );
         first = last = null;
         int k = 1;
         while ( k <= players )
         {
            if ( first == null ) // first data
               first = last = new Link( k, null );
            else // not the first
            {
               last.next = new Link( k, null );
               last = last.next;
            }
            k++;
         }  // end while
         last.next = first;
      }  // end inputList
   
      public void printList( Link last )
      {
         Link current = last;
         while ( current != null )
         {
            System.out.printf( "%d", current.data );
            current = current.next;
            if ( current != null )
               System.out.printf( ", " );
         }
         System.out.printf( "\n" );
      }  // end printList
   
      void playGame( )
      {
			for (int j=1; j<players; j++ )
			{
	         System.out.println("Players left: ");
		 // uncomment this part to see infinite print out     printList ( last );
	         for ( int k=0; k<passes; k++ )
	         {
	            first = first.next;
	            last = last.next;
	         }
	         System.out.println( "Player " + first.data + " is out!" );
	         last.next = first.next;
	         first = last.next;
			}
			System.out.println( "The Winner is player " + first.data + "!" );
      }
   }  // end class LinkedLists

[guzumba15]

Here are my corrections but I still get an infinite print out of remaining players every round of the game... My error is commented in the playGame() method.

// File: LinkedLists.java

import javax.swing.JOptionPane;

   class Link
   {
      public int data;
      public Link next;
   
      public Link( int d, Link n )
      {
         data = d;
         next = n;
      }
      public Link( int d )
      {
         this( d, null );
      }
   }  // end class Link

   public class LinkedLists
   {
      int players, passes;
      Link first = null;
      Link last  = null;
      int length = 0;
   
      public static void main( String [] args )
      {
         new LinkedLists( );
      }
   
      public LinkedLists( )
      {
         inputList( );
         playGame( );
      }  // end main
    
      public void inputList( )
      {
			String input;
			String input2;
         // throw up dialog box to get input
         input = JOptionPane.showInputDialog( "Enter number of players: " );
			players = Integer.parseInt( input );
         input2 = JOptionPane.showInputDialog( "Enter number of passes: " );
			passes = Integer.parseInt( input2 ); 
         first = last = null;
         int k = 1;
         while ( k <= players )
         {
            if ( first == null ) // first data
               first = last = new Link( k, null );
            else // not the first
            {
               last.next = new Link( k, null );
               last = last.next;
            }
            k++;
         }  // end while
         last.next = first;
      }  // end inputList
   
      public void printList( Link first )
      {
         Link current = first;
         while ( current != null )
         {
            System.out.printf( "%d", current.data );
            current = current.next;
            if ( current != null )
               System.out.printf( ", " );
         }
         System.out.printf( "\n" );
      }  // end printList
   
      void playGame( )
      {
			for (int j=1; j<players; j++ )
			{
	         System.out.println("Players left: ");
				// printList ( first );
	         for ( int k=0; k<passes; k++ )
	         {
	            first = first.next;
	            last = last.next;
	         }
	         System.out.println( "Player " + first.data + " is out!" );
	         last.next = first.next;
	         first = last.next;
			}
			System.out.println( "The Winner is player " + first.data + "!" );
      }
   }  // end class LinkedLists

[macosxnerd101]

Your problem is that you are working on a circularly Linked List, so the Tail node points around to the head Node. You need an easy way to detect if you are on the Tail node. My suggestion would be to use a boolean variable to help you here. And inside the while loop, if current == this.last (the instance variable, not the param), then you are on the Tail node, and do not want to go back around. You will also want to adjust the loop condition to account for this boolean.

Duplicate topics merged. Please avoid duplicate posting.

[guzumba15]

Ok I fixed the infinite print out but now I need I need to sort the print out lowest to biggest any ideas?

Thanks for the help I appreciate it!
Andrew

// File: LinkedLists.java

import javax.swing.JOptionPane;

   class Link
   {
      public int data;
      public Link next;
   
      public Link( int d, Link n )
      {
         data = d;
         next = n;
      }
      public Link( int d )
      {
         this( d, null );
      }
   }  // end class Link

   public class LinkedLists
   {
      int players, passes;
		String output = "";
      Link first = null;
      Link last  = null;
      int length = 0;
   
      public static void main( String [] args )
      {
         new LinkedLists( );
      }
   
      public LinkedLists( )
      {
         inputList( );
         playGame( );
      }  // end main
    
      public void inputList( )
      {
			String input;
			String input2;
         // throw up dialog box to get input
         input = JOptionPane.showInputDialog( "Enter number of players: " );
			players = Integer.parseInt( input );
			System.out.println( "The number of players is " + players );
			output += String.format( "The number of players is %d", players );
         input2 = JOptionPane.showInputDialog( "Enter number of passes: " );
			passes = Integer.parseInt( input2 );
			System.out.println( "The number of players is " + passes );
			output += String.format( "\nThe number of passes is %d ", passes );
         first = last = null;
         int k = 1;
         while ( k <= players )
         {
            if ( first == null ) // first data
               first = last = new Link( k, null );
            else // not the first
            {
               last.next = new Link( k, null );
               last = last.next;
            }
            k++;
         }  // end while
         last.next = first;
      }  // end inputList
   
      public void printList( int j )
      {			
        	while ( j < players+1 )
        	{
	           if ( first == null )
			     {
						System.out.print( first.data + " " );
						output += String.format( "%d ", first.data );
				  }
	           else // not the first
	           {
	               last = last.next;
						System.out.print( last.data + " " );
						output += String.format( "%d ", last.data );
	           }
				  j++;
		   }
      }  // end printList
   
      void playGame( )
      {
			for (int j=1; j<players; j++ )
			{
	         System.out.print("Players left: ");
				output += String.format( "\nPlayers left: " );
				printList( j );				
	         for ( int k=0; k<passes; k++ )
	         {
	            first = first.next;
	            last = last.next;
	         }
	         System.out.println( "\nPlayer " + first.data + " is out!" );
				output += String.format( "\nPlayer %d is out!", first.data );
	         last.next = first.next;
	         first = last.next;
			}
			System.out.println( "The Winner is player " + first.data + "!" );
         output += String.format( "\nThe Winner is player %d", first.data );
         JOptionPane.showMessageDialog( null, output );
      }
   }  // end class LinkedLists

[macosxnerd101]

Take a look at Mergesort or Insertion sort. Both are very good algorithms for working with Linked Lists, as they don't take extra time due to the Linked Nodes over array structure.