Java資料結構之單連結串列與OJ題

本篇文章給大家帶來了關於的相關知識，其中主要介紹了關於資料結構的相關內容，包括了單連結串列與OJ題，下面一起來看一下，希望對大家有幫助。

程式設計師必備介面測試偵錯工具：

推薦學習：《》

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;
}
登入後複製