查找单链表倒数第k个节点(算法入门)

public class abc {
    public static void main(String args[]) {
        Hero n1=new Hero(1,"a","aa");
        Hero n2=new Hero(2,"b","bb");
        Hero n3=new Hero(3,"c","cc");
        Hero n4=new Hero(4,"d","dd");
        Lian l=new Lian();
        l.add(n3);
        l.add(n4);
        l.add(n2);
        l.add(n1);
        l.show();    

        System.out.println(l.daoshu(l.getHead(), 2));  //单链表倒数第二个
    }
}
class Lian{
    Hero head=new Hero (0,"","");
    public void add(Hero hero) {
    Hero temp=head;
    while(true) {
        if(temp.next==null) {
            break;
        }
        temp=temp.next;
    }    
        temp.next=hero;
    
}
    
    public void show() {
        Hero temp=head.next;
        if(temp==null) {
            System.out.println("空");
        }
        while(true) {
            if(temp==null) {
                break;
            }
        
        System.out.println(temp);
        temp=temp.next;
        
    }

    }
    
    
    
    public int getLength(Hero head) {   //得到链表有效节点数
        Hero cur=head.next;
        if(head.next==null) {
            System.out.println("空");
        }
        int length=0;
        while(cur!=null) {
            length++;
            cur=cur.next;
            
        }
        return length;
        
    }
    public Hero getHead() {
        return head;
    }


    
    
    
    
    public Hero daoshu(Hero hero,int k) {
        Hero cur=head.next;
        if(head.next==null) {
            return null;
        }
        int size=getLength(head);
        if(k>size||k<=0) {
            return null;
        }
        for(int i=0;i<size-k;i++) {// i从0开始,链表长-k,从正向读取节点
            cur=cur.next;
        }
        return cur;
    }
    
    
    
    
    
    
}

class Hero {
    int no;
    String name;
    String nickname;
    Hero next;
    
    Hero(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }


    public String toString() {
        return "Hero [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }
    }
    
    

结果
  Hero [no=3, name=c, nickname=cc]
Hero [no=4, name=d, nickname=dd]
Hero [no=2, name=b, nickname=bb]
Hero [no=1, name=a, nickname=aa]

Hero [no=2, name=b, nickname=bb]
 
    
    
    
    

上一篇:状态模式


下一篇:java飞机大战