9.java單鏈表初學代碼復現及一些不值一提的小問題（2）

首先寫完了update和delete函數，在之前的鋪墊下。倒是不難，結構和之前的都相同，遍歷找到節點后處理該節點。代碼如下

public void update(teamNode node){
        teamNode temp=head;
        boolean flag=false;
        while(true){

            if (temp.no== node.no){
                flag=true;
                break;
            }
            if(temp.next==null) break;
            temp=temp.next;
        }
        if(!flag){
            System.out.println("無該名次隊伍");
        }else {
            temp.name= node.name;
            temp.point=node.point;
        }
    }
    public void delete(int n){
        teamNode temp=head;
        boolean flag=false;
        while(true){
            if(temp.next==null) break;
            if (temp.next.no== n){
                flag=true;
                break;
            }

            temp=temp.next;
        }
        if(!flag){
            System.out.println("無該名次隊伍");
        }else {
            temp.next=temp.next.next;
        }
    }

此外，還有一些關于單鏈表的題：

1、單鏈表中的有效節點數

思路為遍歷獲取節點個數，帶頭節點的話需要不計入。步驟為：傳入頭節點，判斷是否為空鏈表，不為則創建輔助節點，遍歷整個鏈表。

public static int getlength(teamNode node){
        if(node.next==null){
            return 0;
        }
        int len=0;
        teamNode temp=node;
        while (temp!=null){
            len++;
            temp=temp.next;
        }
        return len;
    }

2、查找單鏈表中的倒數第k個節點。

方法參數為頭節點和一個int代表倒數第幾個節點。得到鏈表長度后，判斷此節點是否存在。若存在則遍歷鏈表到（len-k）個即可得到該節點。未找到的話返回null

public static teamNode findnode(teamNode head,int k){
        if(head.next==null){
            return null;
        }
        int len=getlength(head);
        if(k<=0||k>len) return  null;
        teamNode temp=head.next;
        for (int i=0;i<len-k;i++){
            temp=temp.next;
        }
        return temp;
    }

除了此思路還有一種是用雙指針，讓兩個指針相隔k個位置，當后方的指針指到空時，前指針則指向倒數第k個節點。

3、單鏈表的反轉

思路簡單來說就是新建一個頭節點，將原鏈表的節點一個個取出，用頭插法插入新鏈表，最后將原頭節點與鏈表相連接。

仔細說分為一下幾步，先創建一個新的頭節點，然后開始遍歷原鏈表，拿出節點后永遠放在新鏈表的頭節點之后，即新鏈表有效數據的第一個，最后將原鏈表的頭節點的next連到新鏈表的第一個節點上即可。

此函數最開始不僅要判斷原鏈表是否為空，若原鏈表只有一個節點，其也不用反轉，直接返回原鏈表即可。

在遍歷時，因為被遍歷到的節點需要“拿出來”去改變其next，所以需要一個node來臨時保存其next，讓我們能獲得下一個節點。因為被遍歷到的節點的next要去連接新鏈表的值，若不保存，原來指向的那個節點還未被遍歷到，覆蓋后就無法得到那個節點了。

所以在此處要創建三個節點，一為輔助節點temp，一為臨時保存的next節點，一為新鏈表的頭節點。

public static void reverse(teamNode head){
        if(head.next==null||head.next.next==null){
            return;
        }
        teamNode temp=head.next;
        teamNode next=null;
        teamNode rehead=new teamNode(0,"","");
        while (temp!=null){
            next=temp.next;
            temp.next=rehead.next;
            rehead.next=temp;
            temp=next;
        }
        head.next=rehead.next;
    }

4、從尾到頭打印單鏈表

可以先利用上面的函數反轉了再打印，但會導致原鏈表徹底變化（當然打印完再轉一遍也不是不行。。）但此處選擇用棧 stack來解決。利用其先進后出的原理來解決該題。其中，利用Stack<teamNode> stack=new Stack<teamNode>();可創建棧，棧中的數據形式可自定義，此處為node。

其中，stack.add（）stack.push()為入棧，

stack.pop()為取出并返回棧頂的第一個數據。

因為題目要求為打印，因此不用形成鏈表，有輸出即可。

public  static void reprint(teamNode head){
        if (head!=null){
            return;
        }
        Stack<teamNode> stack=new Stack<teamNode>();
        teamNode temp=head.next;
        while (temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }

寫完這些我可以說是對單鏈表確實的有了更深的理解，在之前就有所了解數據結構的基礎上，可以說是對java中的鏈表有了進一步的了解。但當看到最后一題用的棧時，我在想java中是不是也有這樣已經給我們寫好的基本鏈表定義和一些函數呢，不然難道每次需要用到鏈表的時候都需要重新這樣從頭開始定義一遍嘛。很顯然，我的懶鬼想法是大多數人的想法，java當然有直接的定義和預先寫好的函數。但對于此些API和定義我還尚且不太清楚。

posted @ 2022-03-23 01:06 水煮小白菜閱讀(47) 評論(0) 收藏舉報

刷新頁面返回頂部

codesslave

9.java單鏈表初學代碼復現及一些不值一提的小問題（2）

公告