快捷導(dǎo)航

Java單鏈表的增刪改查與面試題詳解

更新時間：2022年09月24日 16:12:49 作者：小黎的培培筆錄

單鏈表是鏈表的其中一種基本結(jié)構(gòu)。一個最簡單的結(jié)點結(jié)構(gòu)如圖所示，它是構(gòu)成單鏈表的基本結(jié)點結(jié)構(gòu)。在結(jié)點中數(shù)據(jù)域用來存儲數(shù)據(jù)元素，指針域用于指向下一個具有相同結(jié)構(gòu)的結(jié)點。因為只有一個指針結(jié)點，稱為單鏈表

一、單鏈表的增刪改查

1、創(chuàng)建結(jié)點

單鏈表是由結(jié)點連接而成，所以我們首先要創(chuàng)建結(jié)點類，用于對結(jié)點進行操作。定義data屬性表示序號，定義name屬性表示結(jié)點存放的數(shù)據(jù)信息，定義next屬性表示指向下一個結(jié)點。構(gòu)造器只需要放入data屬性和name屬性，重寫toString方法方便打印結(jié)點信息。

public class Node {
    public int data;
    public String name;
    public Node next;
    public Node(int data, String name){
        this.data = data;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", name='" + name + '\'' +
                '}';
    }
}

2、單鏈表的添加操作

首先創(chuàng)建頭結(jié)點

此結(jié)點表示鏈表的頭，不存放實際數(shù)據(jù)的。

private Node head = new Node(0,"");

添加操作

將新的結(jié)點添加到鏈表的尾部，我們首先要遍歷鏈表，找到鏈表的尾部，然后將最后一個結(jié)點的next指向新的結(jié)點，新結(jié)點的next指向NULL，這樣就完成了鏈表的添加操作，這種每次添加到鏈表的尾部的操作稱為尾插法。注意，當我們遍歷鏈表時，需要一個輔助結(jié)點temp來進行遍歷，因為head頭結(jié)點不能動。

public class SingleLinkedList {
    //首先創(chuàng)建頭結(jié)點，此結(jié)點表示鏈表的頭，無具體數(shù)據(jù)
    private Node head = new Node(0,"");
    //添加結(jié)點操作
    public void addData(Node node){
        Node temp = head;
        while (true){
            if (temp.next == null){
                temp.next = node;
                node.next = null;
                break;
            }
            temp = temp.next;
        }
    }
}

3、單鏈表的刪除操作

假設(shè)我們要刪除中間這個結(jié)點，我們只需要將這個結(jié)點的上一個結(jié)點的next指向這個結(jié)點的下一個結(jié)點（也就是將第一個結(jié)點的next指向第三個結(jié)點）。

     public void delData(Node node){
        Node temp = head;
        while (true){
            //如果是要刪除的結(jié)點
            if (temp.next.data == node.data){
                temp.next = temp.next.next;
                break;
            }else if(temp.next == null){
                System.out.println("未找到結(jié)點！");
                break;
            }
            temp = temp.next;
        }
    }

4、單鏈表的有效結(jié)點的個數(shù)

我們可以定義一個計數(shù)的變量count，初始化為0，然后循環(huán)遍歷鏈表，每遍歷到一個結(jié)點，count就加一，這樣就能求出單鏈表的有效個數(shù)。

    public int countData(){
        Node temp = head.next;
        int count = 0;
        while (true){
            if (temp == null){
                break;
            }
            count++;
            temp = temp.next;
        }
        return count;
    }

二、大廠面試題

1、新浪微博：查找單鏈表中倒數(shù)第k個結(jié)點

從上圖可以看出，假設(shè)要找倒數(shù)第2個結(jié)點，我們該怎么做？不難看出，倒數(shù)第二個結(jié)點也是順序的第三個結(jié)點，也就是將倒數(shù)的結(jié)點轉(zhuǎn)換成順序結(jié)點，遍歷鏈表找到順序結(jié)點即可。因為是有明確表示是第幾個結(jié)點，所以我們需要知道結(jié)點的有效個數(shù)，前面我們介紹了有效個數(shù)的求法，直接用即可。當我們要找倒數(shù)第k個結(jié)點，我們可以轉(zhuǎn)換成順序的第（count - k + 1）個結(jié)點。比如：k = 2，count = 4，倒數(shù)第2個結(jié)點也就是順序第（4 - 2 + 1 = 3）個結(jié)點。

    public Node referNode(int n){
        //根據(jù)前面計算有效個數(shù)的方法，求得鏈表總結(jié)點個數(shù)
        int max = countData();
        //計數(shù)
        int count = 1;
        //判斷指定的結(jié)點是否在范圍內(nèi)
        if (!(n >= 1 && n <= max)){
            throw new RuntimeException("沒有此結(jié)點!");
        }
        //輔助結(jié)點
        Node temp = head.next;
        //循環(huán)遍歷查找
        while (true){
            //滿足條件，則是我們要找的結(jié)點
            if (count == (max - n + 1)){
                return temp;
            }else {
                temp = temp.next;
                count++;
            }
        }
    }

2、騰訊面試題：單鏈表的反轉(zhuǎn)

首先創(chuàng)建輔助變量temp用于循環(huán)原來的鏈表，輔助變量temp1記錄temp的下一個位置，每遍歷到一個結(jié)點就插入到新鏈表的頭部，這種方式稱為頭插法。

public void nodeReversal(Node head){
        //如果鏈表為空或鏈表只有一個結(jié)點，則不需要反轉(zhuǎn)
        if (head.next == null || head.next.next == null){
            return;
        }
        //輔助變量temp
        Node temp = head.next;
        //輔助變量temp1
        Node temp1 = null;
        //循環(huán)遍歷
        while (true){
            //退出循環(huán)的條件
            if (temp == null){
                break;
            }
            //首先將temp的下一個結(jié)點給temp1
            temp1 = temp.next;
            //然后將temp的next指向新鏈表頭headReversal的next（頭指向的下一個）
            temp.next = headReversal.next;
            //再然后將新鏈表頭headReversal的next指向temp結(jié)點
            headReversal.next = temp;
            //最后將temp1記錄的結(jié)點賦值給temp
            temp = temp1;
        }
        //遍歷結(jié)束，將新的順序替換原來的順序
        head.next = headReversal.next;
        //顯示鏈表，這個方法需要自己寫
        showList(head);
}

到此這篇關(guān)于Java單鏈表的增刪改查與面試題詳解的文章就介紹到這了,更多相關(guān)Java單鏈表增刪改查內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: