Java如何實現一個單向非循環鏈表

這篇文章主要介紹“Java如何實現一個單向非循環鏈表”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Java如何實現一個單向非循環鏈表”文章能幫助大家解決問題。

1、什么是鏈表？

鏈表是一種物理存儲結構上非連續存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。

通俗點，就是每個元素是一個節點，然后用一個指針域給后面的節點連起來，第一個節點沒有前驅，最后一個節點沒有后繼。

實際中要實現的鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1. 單向、雙向         2. 帶頭、不帶頭         3. 循環、非循環

我們重點講解單向非循環鏈表和雙向非循環鏈表，同時這兩個也是筆試中考的比較多的。

2、實現一個單向非循環鏈表

2.1 實現前的約定

因為鏈表的每個元素是一個節點，所以我們采取內部類的方式，而我們還需要定義一個頭節點的引用，來始終指向頭節點。

public class MySingleList {
    private ListNode head; //引用頭節點
    // 鏈表每個元素是一個節點
    private class ListNode {
        private int val; //存放數據元素
        private ListNode next; //存放下一個節點地址
        //構造方法
        public ListNode(int val) {
            this.val = val;
        }
    }
}

注意：鏈表最少有兩個域，分別是數據域和指針域，當然你也可以有多個數據域和指針域。

我們還需要實現以下幾個常用的方法：

public void addFirst(int data); //頭插法

public void addLast(int data); //尾插法

public boolean addIndex(int index,int data); //任意位置插入,第一個數據節點為0號下標

public boolean contains(int key); //查找關鍵字key是否在單鏈表當中

public void remove(int key); //刪除第一次出現關鍵字為key的節點

public void removeAllKey(int key); //刪除所有值為key的節點

public int size(); //得到單鏈表的長度

public void clear(); //清空鏈表

2.2 addFirst 方法

public void addFirst(int data) {
    ListNode newNode = new ListNode(data); //把傳過來的值放到新的節點中
    newNode.next = this.head; //新節點的next指向頭節點
    this.head = newNode; //使新節點成為頭節點
}

因為head默認是指向空的，當鏈表為null，也不影響這個代碼的執行，不信你下來畫畫圖咯。


2.3 addList 方法

public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    // 如果鏈表為空的情況
    if (this.head == null) {
        this.head = newNode;
        return;
    }
    // 先找到最后一個節點
    ListNode cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = newNode;
}

2.4 addIndex 方法

//任意位置插入,第一個數據節點為0號下標
private ListNode findIndexPrevNode(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
public boolean addIndex(int index,int data) {
    // 判斷index下標的有效性
    if (index < 0 || index > size()) {
        return false;
    }
    // 如果在0下標插入則是頭插
    if (index == 0) {
        addFirst(data); //頭插
        return true;
    }
    // 如果在末尾插入則是尾插
    if (index == size()) {
        addLast(data); //尾插
        return true;
    }

    ListNode newNode = new ListNode(data); //新節點
    // 在中間插入
    ListNode prevNode = findIndexPrevNode(index); //找到index下標的前一個節點
    newNode.next = prevNode.next; //新節點的next被改為index的位置的節點
    prevNode.next = newNode; //index位置前一個節點next被改成新節點
    return true;
}

這個代碼我們首先需要找到index下標的前一個節點，先讓新節點跟index位置的節點綁定起來，在把index的前一個節點與新節點連起來，這個地方說文字是不清楚的，小伙伴們可以下來按照我這個代碼畫圖就能理解了，也可也直接看博主之前的C語言實現數據結構專欄，那里面有圖解哈。

2.5 contains 方法

//查找關鍵字key是否在單鏈表當中
public boolean contains(int key) {
    // 當鏈表為空的情況
    if (this.head == null) {
        return false;
    }
    ListNode cur = this.head;
    // 遍歷列表
    while (cur != null) {
        if (cur.val == key) {
            return true; //找到了返回true
        }
        cur = cur.next;
    }
    return false; //找不到返回false
}

思路很簡單，遍歷一遍鏈表，找到 cur 為空位置，如果有返回true，沒有返回false，交給小伙伴自己下來畫圖咯。

2.6 remove 方法

//刪除第一次出現關鍵字為key的節點
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    ListNode cur = this.head;

    // 如果刪除的是key為頭節點
    if (this.head.val == key) {
        this.head = head.next;
        return;
    }

    // 這里不能是cur!=null, 不然會越界！！！
    while (cur.next != null) {
        // 找到 key 的前一個節點
        if (cur.next.val == key) {
            //當前的cur為key的前一個節點
            cur.next = cur.next.next; //cur鏈接到key的后一個節點
            return;
        }
        cur = cur.next;
    }
}

這里我們需要找到key的前一個節點，然后進行跟key后面的節點綁定即可，當key對應節點沒人引用了，則會被自動回收掉。

2.7 removeAllKey 方法

//刪除所有值為key的節點
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    // 采用前后指針的方法
    ListNode cur = this.head;
    ListNode prev = this.head;
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next; //跳過key節點指向下一個節點
        } else {
            prev = cur;
        }
        cur = cur.next;
    }
    // 判斷第一個節點是不是key
    if (this.head.val == key) {
        this.head = this.head.next; //head指向下一個節點
    }
}

這里大家伙先自己看看，后面講解OJ題會有這道題詳解的。

2.8 size 和 clear 方法

我相信這兩個方法就不需要多說了吧？遍歷？直接頭指針置null？這不就簡單了嗎，這里就不寫了哈，交給各位了！

3、單鏈表OJ題深度解剖

這個才是今天的重頭戲，不是籃球哥不畫圖，是因為前面的圖太簡單了，小伙伴們結合著代碼也能自己畫出來，但是，對于OJ題，大家伙下去還是得畫圖的，相信看完這幾道題，你會愛上數據結構的。

3.1 移除鏈表元素(來源:LeetCode 難度:簡單)

題目：給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，并返回 新的頭節點 。

這個題我們可以用前后指針的思路來做，這樣也比較通俗易懂，更適合初學者，大概的思路是這樣的：我們可以定義一個cur和first的引用，如果碰到相等，也就是first.val == val，我們則讓cur的next指向first的下一個節點，如果不相等，則讓cur走到first的位置，最后first往后走一步，圖解：

這里還沒有完，如果第一個節點的值也是val呢？所以最后我們別忘了進行一個判斷，那么最終的代碼是這樣的：

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    ListNode cur = head;
    ListNode first = head;
    while (first != null) {
        if (first.val == val) {
            cur.next = first.next;
        } else {
            cur = first;
        }
        first = first.next;
    }
    // 判斷頭節點的值是否也是val
    if (head.val == val) {
        head = head.next;
    }
    return head;
}

3.2 反轉鏈表(來源:LeetCode 難度:簡單)

題目：給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。

這個題我們可以先取到頭節點，后續的節點都進行頭插法即可？我們取到頭節點，并且先將頭節點的next置空，但是這樣一來，就找不到后面的節點了，所以我們還需要有一個curNext引用來記錄要反轉節點的下一個節點：

我們的思路是這樣的：首先找到頭節點的next置空，cur走到curNext位置，curNext往前走，使得cur位置的next指向頭節點，頭節點cur再次成為新的頭節點，當curNext走到null的時候循環結束。

public ListNode reverseList(ListNode head) {
    // 空鏈表的情況
    if (head == null) {
        return null;
    }
    ListNode cur = head;
    ListNode curNext = cur.next;
    head.next = null;
    while (curNext != null) {
        cur = curNext;
        curNext = curNext.next;
        cur.next = head;
        head = cur;
    }
    return head;
}

3.4 鏈表中倒數第k個節點

題目：輸入一個鏈表，輸出該鏈表中倒數第k個結點。

這個題也是很簡單的一道題，可以采用前后指針法，先讓first指針走k步，走完之后slow和first一起走，這樣slow和first之間就相差了k步，當first為null時，slow就是倒數第k個節點，在這個過程中，我們還要判斷k的合法性，如果k小于等于0？或者k大于鏈表的長度呢？于是我們就能寫出如下的代碼：

public ListNode FindKthToTail(ListNode head,int k) {
    // 判斷k的合法性
    if (k <= 0 || head == null) {
        return null;
    }
    ListNode first = head;
    ListNode slow = head;
    // 先讓first走k步
    while (k != 0) {
        // k的長度大于鏈表的長度
        if (first == null) {
            return null;
        }
        first = first.next;
        k--;
    }
    // 一起走,當first為null,slow就是倒數第k個節點
    while (first != null) {
        first = first.next;
        slow = slow.next;
    }
    return slow;
}

3.6 鏈表分割(來源:牛客網 難度:較難)

題目：現有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

這個題的思路我們可以這樣做，既然是按照給定的值x進行分割，那么我們設定兩個盤子，盤子A放小于x的節點，盤子B放大于x的節點，最后把這兩個盤子的節點連起來，放回盤子A的頭節點即可！

 public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        ListNode headA = null;
        ListNode headB = null;
        ListNode curA = null;
        ListNode curB = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                // 第一次放入A盤子
                if (headA == null) {
                    headA = cur;
                    curA = cur;
                } else {
                    curA.next = cur;
                    curA = cur;
                }
            } else {
                // 第一次放入B盤子
                if (headB == null) {
                    headB = cur;
                    curB = cur;
                } else {
                    curB.next = cur;
                    curB = cur;
                }
            }
            cur = cur.next;
        }
        // 如果A盤子為空
        if (headA == null) {
            return headB;
        }
        curA.next = headB;
        // 避免B盤子尾節點形成環
        if (headB != null) {
            curB.next = null;
        }
        return headA;
    }

3.7 鏈表的回文結構(來源:LeetCode 難度:較難)

題目：對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。

給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

這個題有要求的，要求空間復雜度為O(1)，并且還得在O(n)的時間復雜度下，那我們就原地解決這個題，我們可以分為三個步驟，首先找到中間節點，然后把中間節點往后的節點進行反轉，最后左右兩個指針同時往中間走。如果光看下面代碼看不懂，可以結合著代碼畫圖才能理解更透徹哦！

public boolean chkPalindrome(ListNode A) {
    if (A == null) {
        return false;
    }
    // 只有一個節點的情況
    if (A.next == null) {
        return true;
    }
    // 首先找到中間節點
    ListNode first = A;
    ListNode slow = A;
    while (first != null && first.next != null) {
        first = first.next.next;
        slow = slow.next;
    }
    // 走到這,slow是鏈表的中間節點,采用頭插法反轉slow后續的節點
    first = slow.next;
    ListNode cur = slow;
    while (first != null) {
        cur = first;
        first = first.next;
        cur.next = slow; //鏈接前一個節點
        slow = cur; //更新頭節點的位置
    }
    // 走到這,反轉完畢,cur指向最后一個節點,讓slow等于A,往中間找
    slow = A;
    while (slow != cur) {
        if (slow.val != cur.val) {
            return false;
        }
        // 偶數的情況下需要特殊判斷
        if (slow.next == cur) {
            return true;
        }
        slow = slow.next;
        cur = cur.next;
    }
    return true;
}

3.8 相交鏈表(來源:LeetCode 難度:簡單)

題目：給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null 。

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

這個題我們可以這樣做，長鏈表先走兩個鏈表的長度差的步數，因為相交之后的節點都是一樣的個數，所以走了差值后，就兩個鏈表一起往后走，相等了則就是相交節點。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode longList = headA; //longList始終記錄長的鏈表
    ListNode shortList = headB;
    // 分別求出兩個鏈表的長度
    int lenA = 0;
    int lenB = 0;
    ListNode cur = headA;
    while (cur != null) {
        lenA++;
        cur = cur.next;
    }
    cur = headB;
    while (cur != null) {
        lenB++;
        cur = cur.next;
    }
    int len = lenA - lenB;
    // 如果B鏈表長于A鏈表
    if (len < 0) {
        // 修正相差長度
        len = lenB - lenA;
        longList = headB; //longList始終記錄長的鏈表
        shortList = headA;
    }
    // 讓長鏈表先走差值len步,然后同步走,相等了即為相交節點
    while (len != 0) {
        longList = longList.next;
        len--;
    }
    while (longList != shortList) {
        longList = longList.next;
        shortList = shortList.next;
    }
    // 如果兩個鏈表走到了null,則沒有中間節點返回null,如果有,返回任意一個即可
    return longList;
}

關于“Java如何實現一個單向非循環鏈表”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。