Java solution using circular linked list.


  • -1
    R

    Java's LinkedList is not circular, and cannot do remove operation in O(1) time, so I made my own simple circular LinkedList.

    public String predictPartyVictory(String senate) {
        char[] sen=senate.toCharArray();
        int R=0,D=0;
        //build the begin node of the list
        Player begin=new Player(sen[0]=='R'?true:false);
        if(sen[0]=='R')R++;
        else D++;
        Player cur=begin;
        //construct circular list
        for(int i=1;i<sen.length;i++){
            if(sen[i]=='R'){
                cur.next=new Player(true);
                R++;
            }
            else{
                cur.next=new Player(false);
                D++;
            }
            cur=cur.next;
        }
        cur.next=begin; //make it cirsular
        //loop the linked list till one side goes to 0;
        while(R!=0&&D!=0){
            cur=begin.next;
            Player prev=begin;
            while(cur.Radiant==begin.Radiant){
                cur=cur.next;
                prev=prev.next;
            }
            prev.next=cur.next;
            if(begin.Radiant)D--;
            else R--;
            begin=begin.next;
        }
        return R==0?"Dire":"Radiant";
    }
    
    
    public class Player{
        Player next;
        boolean Radiant;
        Player(boolean side){
            Radiant=side;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.