資料結構和演算法之單鏈表練習

三道大廠面試題：

【新浪面試題】查找單鏈表中的倒數第k個結點
【騰訊面試題】單鏈表的反轉
【百度面試題】從尾到頭列印單鏈表

1、先上神器：

lombok，在pom里面加入依賴，并在idea中下載lombok插件，然后就可以直接使用啦~

        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.16</version>
        </dependency>

2、用一個heroNode類模擬節點

@Data
@NoArgsConstructor
class HeroNode{
    private int no;
    private String name;
    private String nickname; //昵稱
    private HeroNode next;//指向下一個節點編號

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    public String toString(){
        return"HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
        //重寫tostring方法，方便展示輸出資料
    }
}

3、單鏈表方法的實作

//鏈表操作
class SingleLinkedTest{
    //鏈表的頭部固定，定義一個頭節點，資料為空
    private HeroNode head = new HeroNode(0,"","");
    public HeroNode getHead() {
        return head;
    }

    //將節點掛上鏈表
    public void addNode(HeroNode heroNode){
        //先找到尾節點，然后把新節點掛到尾節點上
        //定義輔助節點temp
        HeroNode temp  = head;
        while (true){
            if (temp.getNext() == null){ //當輔助節點的下一個節點為空時，表示找到了最后一個節點
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(heroNode);
    }

    //有序的將節點加入鏈表
    public void addOrderNode(HeroNode heroNode){
        //定義輔助節點temp
        HeroNode temp  = head;
        while (true){
            if (temp.getNext() == null){ //當輔助節點的下一個節點為空時，表示已經到了最后一個節點
                temp.setNext(heroNode);
                break;
            }
            //當輔助節點的下一個節點的編號大于當前編號，則找到了插入的位置
            if (heroNode.getNo() < temp.getNext().getNo()){
                heroNode.setNext(temp.getNext());
                temp.setNext(heroNode);
                break;
            }
            temp = temp.getNext();

        }
    }

    //獲取節點個數，不包括頭結點
    public void getNodeCount(){
        HeroNode temp = head;
        int count = 0;
        while (true){
            if (temp.getNext() == null){
                break;
            }
            count++;
            temp = temp.getNext();
        }
        System.out.println("節點的個數為："+count);
    }

    //節點反轉
    public SingleLinkedTest reversalLink(SingleLinkedTest singleLinkedTest){
        SingleLinkedTest singleLinkedTestTemp = new SingleLinkedTest();
        HeroNode temp ;//輔助節點
        HeroNode temp01 = singleLinkedTest.getHead().getNext(); //要反轉鏈表的頭部
        while (true){
            if (temp01 == null){
                break; //舊鏈表空了，表示全部反轉完了
            }
            //反轉鏈接，所以所有新獲取的節點，每次都放到head后面
            temp = singleLinkedTestTemp.getHead().getNext(); //總是指向新鏈表的下一個節點
            singleLinkedTestTemp.getHead().setNext(temp01);
            temp01=temp01.getNext();
            singleLinkedTestTemp.getHead().getNext().setNext(temp);
        }
        return singleLinkedTestTemp;
    }

    //獲取倒數第K個節點
    public void getKNode(SingleLinkedTest singleLinkedTest,int k){
        int count = 0;
        HeroNode temp = singleLinkedTest.getHead(); //輔助節點
        if(temp.getNext() == null){
            System.out.println("鏈表為空，無法獲取");
            return;
        }
        while (true){
            if (count == k){
                System.out.printf("倒數第%d個節點是：\n"+temp,k);
                break;
            }
            temp = temp.getNext();
            count++;
        }
    }

    //展示鏈表所有資料
    public void showNode(SingleLinkedTest  singleLinkedTest){
        //定義輔助節點temp
        HeroNode temp = singleLinkedTest.getHead();
        if (temp.getNext() == null){
            System.out.println("當前鏈表為空~");
            return;
        }
        while (true){
            if (temp.getNext() == null){
                break;
            }
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }
}

4、開始測驗

public class SingleLinked {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "一號", "小明");
        HeroNode heroNode2 = new HeroNode(2, "二號", "小紅");
        HeroNode heroNode3 = new HeroNode(3, "三號", "小君");
        HeroNode heroNode4 = new HeroNode(4, "四號", "小帥");
        HeroNode heroNode5 = new HeroNode(5, "五號", "小鹿");
        SingleLinkedTest singleLinkedTest = new SingleLinkedTest();
//        singleLinkedTest.addNode(heroNode1);//按照執行順序添加節點
//        singleLinkedTest.addNode(heroNode2);
//        singleLinkedTest.addNode(heroNode3);
        singleLinkedTest.addOrderNode(heroNode1);//有序的添加節點
        singleLinkedTest.addOrderNode(heroNode5);
        singleLinkedTest.addOrderNode(heroNode4);
        singleLinkedTest.addOrderNode(heroNode3);
        singleLinkedTest.addOrderNode(heroNode2);
        singleLinkedTest.showNode(singleLinkedTest);//鏈表資料展示

        //求鏈表節點個數
        singleLinkedTest.getNodeCount();

        //求倒數第K個節點  + 鏈表反轉 + 從尾到頭列印
        SingleLinkedTest singleLinkedTestReversal =
                singleLinkedTest.reversalLink(singleLinkedTest);//得到反轉后的鏈表
        singleLinkedTest.showNode(singleLinkedTestReversal);//展示反轉后的鏈表資料
        singleLinkedTest.getKNode(singleLinkedTestReversal,5);//得到反轉后的鏈表中第5條資料
    }
}

5、結果：

HeroNode[no=1,name=一號,nickname=小明]
HeroNode[no=2,name=二號,nickname=小紅]
HeroNode[no=3,name=三號,nickname=小君]
HeroNode[no=4,name=四號,nickname=小帥]
HeroNode[no=5,name=五號,nickname=小鹿]
節點的個數為：5
HeroNode[no=5,name=五號,nickname=小鹿]
HeroNode[no=4,name=四號,nickname=小帥]
HeroNode[no=3,name=三號,nickname=小君]
HeroNode[no=2,name=二號,nickname=小紅]
HeroNode[no=1,name=一號,nickname=小明]
倒數第5個節點是：
HeroNode[no=1,name=一號,nickname=小明]

標籤：其他

上一篇：菜鳥看過來！新的一年，這幾點雷區別再踩了

下一篇：談一下稀疏陣列