用java对链表的算法的操作,不行,请高手指点!!

Question

题目如下:(主要是想请教为什么用链表的方式不能解决问题,并不是想解决这条题,所以大家不要讲其它的方式)
有10000个人，按1、2、1、2的顺序排，数1的站出来离开队，2的排回原队，并在次数1、2、1、2的顺序报数，同样1的离队，2的留下，如此类推，到最后留下来的号码是多少？
public class Mylist {
public Mylist(){
Linknode head=new Linknode(1,null);
Linknode current=head;
for(int i=2;i<=10000;i++){
Linknode temp=new Linknode(i,null);
current.nextnode=temp;
current.origin=i;
System.out.println("head.origin="+head.origin+"  head.nextnode.origin="+head.nextnode.origin);
System.out.println("current.origin="+current.origin+"  current.nextnode.origin="+current.nextnode.origin);

}

current.nextnode=head;//到这一步为止,下面这个while语句没执行,为什么?
while(head!=head.nextnode){
head=head.nextnode;
head.nextnode=head.nextnode.nextnode;
} }

private class Linknode{
private int origin;
private Linknode nextnode;
Linknode(){
}
}
Linknode(int number,Linknode node){
this.origin=number;
this.nextnode=node;
}
Linknode get_nextnode(){
return this.nextnode;
}
void set_nextnode(Linknode node){
this.nextnode=node;
} 
}
}

Answer 1

远看貌似算法有问题...
current.nextnode=head 
while(head!=head.nextnode){...}这... 真以为nextnode是指针咩...

Answer 2

lz的代码怎么看都不像是Java咩...

Answer 3

那你要指出问题是哪里,应怎改?是否java不支持指针的问题?

Answer 4

 class Mylist 
 { 
public Mylist()
{ 
Linknode head=new Linknode(1,null,null); 
Linknode current=head; 
for(int i=2;i <=10000;i++)
{ 
Linknode temp=new Linknode(i,null,null); 
current.set_nextnode(temp); 
temp.setLastNode(current);
current = temp;
} 
current.set_nextnode(head);//到这一步为止,下面这个while语句没执行,为什么? 
head.setLastNode(current);
System.out.println(head.origin);
while(head!=head.get_nextnode())
{
head = head.get_nextnode().get_nextnode();
  head.getLastNode().getLastNode().deletCurNode();
} 
System.out.println(head.origin);
}  private class Linknode
{ 
public  int origin; 
private  Linknode nextnode; 
private  Linknode lastnode;
private Linknode lasttmp,nexttmp;
public Linknode()
{ 
} 
public Linknode(int number,Linknode next,Linknode last)
{ 
this.origin=number; 
this.nextnode=next;
this.lastnode = last; 
} 
public  Linknode get_nextnode()
{ 
return this.nextnode; 
} 
public Linknode getLastNode()
{
return this.lastnode;
}
public void set_nextnode(Linknode node)
{ 
this.nextnode=node; 
}
public void setLastNode(Linknode last)
{
this.lastnode = last;
}

public void deletCurNode()
{
lasttmp = this.getLastNode();
nexttmp = this.get_nextnode();
lasttmp.set_nextnode(nexttmp);
nexttmp.setLastNode(lasttmp);
}
} 
public static void main(String args[])
{
new Mylist();
}
}
done! 最后输出最后 一个人的ID;
几个问题说下:
1."到这一步为止,下面这个while语句没执行,为什么?"  在你原来的循环中,current并没有往后移位,导致你一直都在改变
head节点.
2.增加lastNode指针,因为按LZ原来的想法是,一开始把偶数留下,12345...变成246...但,你的做法成功的把3,5,7...跳过了,但1这个节点没有跳过,所有10000.next还是等于1(原本应等于2),这样会导致循环一圈后,多出一个节点,计数错误.所以我加了一个lastNode节点,用来保证不会出现这种情况,(你试着用10来试试就知道了,没有lastNode的情况最后一个节点是6(错误),设定了lastNode的情况,最后一个节点是4(正确))
3.对于private的属性的调用,虽然我也不知道为什么这里可以直接使用XXX.nextnode;xxx.lastnode(可能是因为内部类吧),但最好还是用方法来调用(XXX.getNextNode();XXX.getLastNode());这只是一个习惯问题.毕竟你也已经实现了这几个方法了.

Answer 5

while(head!=head.nextnode)这样
while(!head.equal(head.nextnode)){...}

Answer 6

public class Mylist 
{
  private static final int SIZE = 100;  public static void main(String[] args) 
  {
    Linknode head = new Linknode(1, null);
    Linknode current = head;
    Linknode newl = null; 
    for(int i=2;i<=SIZE;i++)
    {
      Linknode temp = new Linknode(i,null);
      current.setNextnode(temp);
      current = temp;
    }
    while(head.haseNext())
    {
      current = head;
      int i = 1;
      while( current!=null )
      {
        if(current==head && current.getOrigin()%2!=0)
        {
          newl = current.getNextnode();
          newl.setNextnode(current.getNextnode().getNextnode());
          newl.setOrigin(i);
          current = newl.getNextnode();
          head = newl;
        }
        else if(current.getOrigin()%2!=0)
        {
          newl = current.getNextnode();
          newl.setNextnode(current.getNextnode().getNextnode());
          newl.setOrigin(i);
          current = newl.getNextnode();
        }
        else
        {
          current.setOrigin(i);
          current = current.getNextnode();
        }
        i++;
      }
    }
    System.out.print("head.origin=");
    System.out.println(head.getId());
  }
}class Linknode 
{
  private static int index = 0;
  private int id = 1;
  private int origin = -1;
  private Linknode nextnode = null;  public Linknode(int number, Linknode node) 
  {
    this.origin = number;
    this.nextnode = node;
    this.id = index++;
  }

  public boolean haseNext()
  {
    if(this.nextnode==null)
    {
      return false;
    }
    else
    {
      return true;
    }
  }  public int getId() 
  {
    return id;
  }
  public int getOrigin() 
  {
    return origin;
  }
  public void setOrigin(int origin) 
  {
    this.origin = origin;
  }
  public Linknode getNextnode() 
  {
    return nextnode;
  }
  public void setNextnode(Linknode nextnode) 
  {
    this.nextnode = nextnode;
  }
}
Java指针类咩.

Answer 7

(1)对不起大家,这道题我是有个地方写错了(在for那里),所以才不成功(可能没睡好觉吧!!)(2)回复 六楼,ssqmnlin
   其实当初的思想是这样的:先new 一个结点,赋值给另一个结点current(
   Linknode head=new Linknode(1,null); 
   Linknode current=head; 
   ),然后做for(),搞9999个结点出来,再把第10000个结点的nextnode指向head,这样就形成10000个结点了(一条头 尾连接的链表),接着做while(),所以其实是不用lastnode的(3)回复7楼的,你以为是string啊,equal(4)回复8楼(间隙的妖怪),thank you!!
   不过你思路其实是数组的思路来的,还不如改成数组来做,按你的链表做法太复杂了(5)所以我修正后的结果如下:(如还觉得还有地方不对的请指教,或还有比链表更简单的方法(我觉得链表是最简单))public class Mylist {
public Mylist(){
Linknode head=new Linknode(1,null);
Linknode current=head;
for(int i=2;i<=100;i++){
Linknode temp=new Linknode(i,null);
current.nextnode=temp;
current=current.nextnode;
System.out.println("head.origin="+head.origin+"  head.nextnode.origin="+head.nextnode.origin);
System.out.println("current.origin="+current.origin+"  current.nextnode.origin=");

}

current.nextnode=head;
while(head!=head.nextnode){
head=head.nextnode;
head.nextnode=head.nextnode.nextnode;
}
System.out.println(head.origin);
}

private class Linknode{
private int origin;
private Linknode nextnode;
Linknode(){
}

Linknode(int number,Linknode node){
this.origin=number;
this.nextnode=node;
}
Linknode get_nextnode(){
return this.nextnode;
}
void set_nextnode(Linknode node){
this.nextnode=node;
} 
}
}

Answer 8

我看了你的程序,还是不正确的.
你可以增加一个程序入口public static void main(String args[])
{
   new MyList();
}并把for(int   i=2;i <=100;i++)改成
for(int   i=2;i <=10;i++)
10个数的话,你应该可以算出来最后一个结果是4,但你的程序得出的结果是6!!
这是就是因为你的头结点(也就是ID为1的这个节点),并没有排除出链表外,这也就是我加入lastNode的主要原因

Answer 9

我认为楼主是这种表示方法, 利用单链表解决
 class MylistRevised
 { 
    public MylistRevised()
    { 
        Linknode head=new Linknode(1,null); 
        Linknode current=head; 
Linknode temp;

        for(int i=2;i <=10000;i++)
        { 
            temp=new Linknode(i,null); 
            current.set_nextnode(temp); 
            current = temp;    

        } temp=head;
while(true)
{
if(temp.get_nextnode()==null)
System.out.println( "current.origin= "+temp.origin);
else
System.out.println( "current.origin= "+temp.origin+ "  current.nextnode.origin= "+temp.get_nextnode().origin); 
if(temp.get_nextnode()==null) break;
temp=temp.get_nextnode();
}
 
        System.out.println(head.origin);
        while(head.get_nextnode()!=null)
        {
           
head = head.get_nextnode(); 
current= head.get_nextnode();
temp=head;
            while(current!=null){
if(current.get_nextnode()==null || current.get_nextnode().get_nextnode()==null)
{
    current.deletCurNode(temp);
break;
}
               
   current.deletCurNode(temp);
   temp=temp.get_nextnode();
   current=temp.get_nextnode();    
}        
} 
        System.out.println(head.origin);
    }     private class Linknode
    { 
        public  int origin; 
        private  Linknode nextnode, temp; 
        private Linknode lasttmp,nexttmp;
        public Linknode()
        { 
        } 
        public Linknode(int number,Linknode next)
        { 
            this.origin=number; 
            this.nextnode=next;
            
        } 
        public  Linknode get_nextnode()
        { 
            return this.nextnode; 
        } 
        
        public void set_nextnode(Linknode node)
        { 
            this.nextnode=node; 
        }
       
        
        public void deletCurNode(Linknode temp)
        {
            temp.set_nextnode(this.get_nextnode());
            
        }
    } 
    public static void main(String args[])
    {
        new MylistRevised();
    }

}
 

Answer 10

单链表不代表不能是圈!
而且你看看LZ在1楼写的代码
current.nextnode=head;
//虽然代码是不正确的,但表达的意思就是首尾相接的圈链或者看看LZ在11楼的回复
"
其实当初的思想是这样的:先new   一个结点,赋值给另一个结点current( 
      Linknode   head=new   Linknode(1,null);   
      Linknode   current=head;   
      ),然后做for(),搞9999个结点出来,再把第10000个结点的nextnode指向head,这样就形成10000个结点了(一条头   尾连接的链表),...
"

Answer 11

新手小白提问：
 java中没有指针对吧？但据我的理解 链表就是指针连接起来的结点的集合。链表的存储结构在java中是否和c中一样？