一簡介

單鏈表中的每個結點不僅包含值，還包含鏈接到下一個結點的引用字段。

image

1.1 結點結構

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

1.2 操作

與數組不同，我們無法在常量時間內訪問單鏈表中的隨機元素。
如果我們想要獲得第 i 個元素，我們必須從頭結點逐個遍歷。我們按索引來訪問元素平均要花費 O(N) 時間，其中 N 是鏈表的長度。

1.3 添加操作 - 單鏈表

如果我們想在給定的結點 prev 之后添加新值，我們應該：

1. 使用給定值初始化新結點 cur；
1. 將 cur 的“next”字段鏈接到 prev 的下一個結點 next；
1. 將 prev 中的“next”字段鏈接到 cur 。

與數組不同，我們不需要將所有元素移動到插入元素之后,因此，您可以在 O(1) 時間復雜度中將新結點插入到鏈表中，這非常高效。

1.4 刪除操作 - 單鏈表

如果我們想從單鏈表中刪除現有結點 cur，可以分兩步完成：

1. 找到 cur 的上一個結點 prev 及其下一個結點 next；
1. 接下來鏈接 prev 到 cur 的下一個節(jié)點 next。
第一步中，我們需要找出 prev 和 next。使用 cur 的參考字段很容易找出 next，但是，我們必須從頭結點遍歷鏈表，以找出 prev，它的平均時間是 O(N)，其中 N 是鏈表的長度。因此，刪除結點的時間復雜度將是 O(N)。
空間復雜度為 O(1)，因為我們只需要常量空間來存儲指針。

1.5 設計鏈表

設計鏈表的實現。您可以選擇使用單鏈表或雙鏈表。

單鏈表中的節(jié)點應該具有兩個屬性：val 和 next。
- val 是當前節(jié)點的值
- next 是指向下一個節(jié)點的指針/引用

如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(jié)點都是 0-index 的。
在鏈表類中實現這些功能：

get(index)：獲取鏈表中第 index 個節(jié)點的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節(jié)點。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。
addAtTail(val)：將值為 val 的節(jié)點追加到鏈表的最后一個元素。
addAtIndex(index,val)：在鏈表中的第 index 個節(jié)點之前添加值為 val 的節(jié)點。如果 index 等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點。

二雙指針技巧

2.1 給定一個鏈表，判斷鏈表中是否有環(huán)。

可能已經使用哈希表提出了解決方案

想象一下，有兩個速度不同的跑步者。如果他們在直路上行駛，快跑者將首先到達目的地。但是，如果它們在圓形跑道上跑步，那么快跑者如果繼續(xù)跑步就會追上慢跑者。
這正是我們在鏈表中使用兩個速度不同的指針時會遇到的情況：
- 1. 如果沒有環(huán)，快指針將停在鏈表的末尾。
- 1. 如果有環(huán)，快指針最終將與慢指針相遇。

所以剩下的問題是：這兩個指針的適當速度應該是多少？

一個安全的選擇是每次移動慢指針一步，而移動快指針兩步。每一次迭代，快速指針將額外移動一步。如果環(huán)的長度為 M，經過 M 次迭代后，快指針肯定會多繞環(huán)一周，并趕上慢指針。
親參考2.2圖

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                return true;
            }
        }
        return false;
        
    }
}

2.2 返回鏈表開始入環(huán)的第一個節(jié)點

給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回 null。

解題，有了2.1的基礎，來計算一下。

QQ截圖20180908102303.png

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                break;
            }
        }

        while (head != null && slow != null) {
            if (head.equals(slow)) {
                return slow;
            }
            head = head.next;
            slow = slow.next;
        }

        return null;

    }
}

2.3 相交鏈表

(判斷是否相交，可以遍歷兩個鏈表，看最后一個節(jié)點是否相等)
編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。
例如，下面的兩個鏈表：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在節(jié)點 c1 開始相交。
注意：

如果兩個鏈表沒有交點，返回 null.
在返回結果后，兩個鏈表仍須保持原有的結構。
可假定整個鏈表結構中沒有循環(huán)。
程序盡量滿足 O(n) 時間復雜度，且僅用 O(1) 內存。

    /**
     * 返回相交單向鏈表的交點
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        //記錄鏈表的長度
        int lenA = 1;
        ListNode tempA = headA;
        while (tempA.next != null) {
            lenA++;
            tempA = tempA.next;
        }

        int lenB = 1;
        ListNode tempB = headB;
        while (tempB.next != null) {
            lenB++;
            tempB = tempB.next;
        }

        //判斷鏈表是否相交，不想交直接返回null
        if (!tempA.equals(tempB)) {
            return null;
        }

        //截取后半段，相同長度的鏈表
        int reduseCount = lenA - lenB;

        tempA = headA;
        tempB = headB;
        if (reduseCount > 0) {
            for (int i = 0; i < reduseCount; i++) {
                tempA = tempA.next;
            }
        } else {
            reduseCount = Math.abs(reduseCount);
            for (int i = 0; i < reduseCount; i++) {
                tempB = tempB.next;
            }
        }

        //循環(huán)遍歷找到交點
        while (tempB != null && tempA != null) {
            if (tempB.equals(tempA)) {
                return tempB;
            }
            tempA = tempA.next;
            tempB = tempB.next;
        }

        return null;
    }

2.4 刪除鏈表的倒數第N個節(jié)點

給定一個鏈表，刪除鏈表的倒數第 n 個節(jié)點，并且返回鏈表的頭結點。
示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.

說明：
給定的 n 保證是有效的。
進階：
你能嘗試使用一趟掃描實現嗎？
解題思路
- 典型的利用雙指針法解題。首先讓指針first指向頭節(jié)點，然后讓其向后移動n步，接著讓指針sec指向頭結點，并和first一起向后移動。當first的next指針為NULL時，sec即指向了要刪除節(jié)點的前一個節(jié)點，接著讓first指向的next指針指向要刪除節(jié)點的下一個節(jié)點即可。
- 注意如果要刪除的節(jié)點是首節(jié)點，那么first向后移動結束時會為NULL，這樣加一個判斷其是否為NULL的條件，若為NULL則返回頭結點的next指針。

    /**
     * 刪除鏈表的倒數第 n 個節(jié)點
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        if (n == 0) {
            return null;
        }

        ListNode first = head;
        ListNode sec = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }

        while (first != null && first.next != null) {
            first = first.next;
            sec = sec.next;
        }

        if (sec.next == null) {
            return null;
        }


        sec.next = sec.next.next;
        return head;
    }

2.5小結

2.5.1 提示

1. 在調用 next 字段之前，始終檢查節(jié)點是否為空。
- 獲取空節(jié)點的下一個節(jié)點將導致空指針錯誤。例如，在我們運行 fast = fast.next.next 之前，需要檢查 fast 和 fast.next 不為空。
1. 仔細定義循環(huán)的結束條件。

2.5.2 復雜度分析

空間復雜度分析容易。如果只使用指針，而不使用任何其他額外的空間，那么空間復雜度將是 O(1)。

三經典問題

3.1 反轉鏈表

一種解決方案是按原始順序迭代結點，并將它們逐個移動到列表的頭部。
單鏈表--反轉

3.2 刪除鏈表中的節(jié)點

刪除鏈表中等于給定值 val 的所有節(jié)點。
示例:

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

代碼

    /**
     * 刪除鏈表中的節(jié)點
     */
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        //定義前指針 是為了刪除節(jié)點
        ListNode pre = null;
        
        //定義next是為了指針后移
        ListNode next;
        
        for (ListNode i = head; i != null; i = next) {
            next = i.next;
            if (i.val == val) {
                //這個判斷說明頭一個節(jié)點，就需要刪除，因此頭指針后移
                if (head.equals(i)) {
                    head = head.next;
                }

                //前節(jié)點next指向后節(jié)點
                if (pre != null) {
                    pre.next = i.next;
                }

                i.next = null;
            } else {
                pre = i;
            }
        }

        return head;
    }

3.3 奇偶鏈表

給定一個單鏈表，把所有的奇數節(jié)點和偶數節(jié)點分別排在一起。請注意，這里的奇數節(jié)點和偶數節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節(jié)點總數。
示例 1:

輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

示例 2:

輸入: 2->1->3->5->6->4->7->NULL 
輸出: 2->3->6->7->1->5->4->NULL

說明:

應當保持奇數節(jié)點和偶數節(jié)點的相對順序。
鏈表的第一個節(jié)點視為奇數節(jié)點，第二個節(jié)點視為偶數節(jié)點，以此類推。
代碼

    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;


        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

3.4 回文鏈表

請判斷一個鏈表是否為回文鏈表。
示例 1:

輸入: 1->2
輸出: false

示例 2:

輸入: 1->2->2->1
輸出: true

進階：
你能否用 O(n) 時間復雜度和 O(1) 空間復雜度解決此題？

    /**
     * 斷一個鏈表是否為回文鏈表
     * 輸入: 1->2->2->1
     * 輸出: true
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode reverseNode = null;//指向反轉的鏈表
        ListNode nomalNode;//指向后面后半截鏈表

        if (head.next.next == null) {
            reverseNode = head;
            nomalNode = head.next;
            reverseNode.next = null;
        } else {
            //快慢指針找中間值
            //順便反轉前半截鏈表
            ListNode slow = head;
            ListNode fast = head;

            ListNode tempSlow;
            ListNode tempFast;


            while (fast.next != null && fast.next.next != null) {
                tempSlow = slow.next;
                tempFast = fast.next.next;

                slow.next = reverseNode;
                reverseNode = slow;

                slow = tempSlow;
                fast = tempFast;
            }


            tempSlow = slow.next;
            slow.next = reverseNode;
            reverseNode = slow;


            //考慮鏈表是奇數長度鏈表
            if (fast.next == null) {
                reverseNode = reverseNode.next;
            }

            nomalNode = tempSlow;
        }

        //遍歷后半截找不同
        while (nomalNode != null && reverseNode != null) {
            if (nomalNode.val != reverseNode.val) {
                return false;
            }
            nomalNode = nomalNode.next;
            reverseNode = reverseNode.next;
        }

        return true;

3.5 小結

快慢指針：可以找環(huán)，可以找中間點，可以相差n個節(jié)點的鏈表

四雙鏈表

4.1 簡介 - 雙鏈表

4.1.1 定義

雙鏈表以類似的方式工作，但還有一個引用字段，稱為“prev”字段。有了這個額外的字段，您就能夠知道當前結點的前一個結點。

image

4.1.2 結點結構

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

與單鏈接列表類似，我們將使用頭結點來表示整個列表。

4.1.3 操作

與單鏈表類似，我們將介紹在雙鏈表中如何訪問數據、插入新結點或刪除現有結點。

我們不能在常量級的時間內訪問隨機位置。
我們必須從頭部遍歷才能得到我們想要的第一個結點。
在最壞的情況下，時間復雜度將是 O(N)，其中 N 是鏈表的長度。

4.2 添加操作 - 雙鏈表

如果我們想在現有的結點 prev 之后插入一個新的結點 cur，我們可以將此過程分為兩個步驟：

鏈接 cur 與 prev 和 next，其中 next 是 prev 原始的下一個節(jié)點；

image
用 cur 重新鏈接 prev 和 next。

image

4.3 刪除操作 - 雙鏈表

如果我們想從雙鏈表中刪除一個現有的結點 cur，我們可以簡單地將它的前一個結點 prev 與下一個結點 next 鏈接起來。

與單鏈表不同，使用“prev”字段可以很容易地在常量時間內獲得前一個結點。

因為我們不再需要遍歷鏈表來獲取前一個結點，所以時間和空間復雜度都是O(1)。

五、小結 - 鏈表

5.1 小結

5.1.1 回顧

讓我們簡要回顧一下單鏈表和雙鏈表的表現。
它們在許多操作中是相似的。

它們都無法在常量時間內隨機訪問數據
它們都能夠在 O(1) 時間內在給定結點之后或列表開頭添加一個新結點。
它們都能夠在 O(1) 時間內刪除第一個結點

但是刪除給定結點(包括最后一個結點)時略有不同。

在單鏈表中，它無法獲取給定結點的前一個結點，因此在刪除給定結點之前我們必須花費 O(N) 時間來找出前一結點。
在雙鏈表中，這會更容易，因為我們可以使用“prev”引用字段獲取前一個結點。因此我們可以在 O(1) 時間內刪除給定結點。

5.1.2 對照

這里我們提供鏈表和其他數據結構（包括數組，隊列和棧）之間時間復雜度的比較：

image

經過這次比較，我們不難得出結論：

如果你需要經常添加或刪除結點，鏈表可能是一個不錯的選擇。
如果你需要經常按索引訪問元素，數組可能是比鏈表更好的選擇。

5.2 合并兩個有序鏈表

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

   /**
     * 合并兩個有序鏈表
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        ListNode mergeListNode;
        if (l1.val > l2.val) {
            mergeListNode = l2;
            temp2 = l2.next;
        } else {
            mergeListNode = l1;
            temp1 = l1.next;
        }
        ListNode mergeListNodePointer = mergeListNode;


        //每次循環(huán)只前進一個指針
        while (temp1 != null && temp2 != null) {
            if (temp1.val > temp2.val) {
                mergeListNodePointer.next = temp2;
                mergeListNodePointer=mergeListNodePointer.next;
                temp2 = temp2.next;
            } else {
                mergeListNodePointer.next = temp1;
                mergeListNodePointer=mergeListNodePointer.next;
                temp1 = temp1.next;
            }
        }

        //將剩余的節(jié)點拼接起來
        if (temp1 != null) {
            mergeListNodePointer.next = temp1;
        }

        if (temp2 != null) {
            mergeListNodePointer.next = temp2;
        }

        return mergeListNode;
    }

5.3 兩數相加

java 鏈表兩數相加

參考

鏈表
 http://www.itdecent.cn/p/ef71e04241e4

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數據結構--鏈表(java)

數據結構--鏈表(java)

一簡介

1.1 結點結構

1.2 操作

1.3 添加操作 - 單鏈表

1.4 刪除操作 - 單鏈表

1.5 設計鏈表

二雙指針技巧

2.1 給定一個鏈表，判斷鏈表中是否有環(huán)。

2.2 返回鏈表開始入環(huán)的第一個節(jié)點

2.3 相交鏈表

2.4 刪除鏈表的倒數第N個節(jié)點

2.5小結

2.5.1 提示

2.5.2 復雜度分析

三經典問題

3.1 反轉鏈表

3.2 刪除鏈表中的節(jié)點

3.3 奇偶鏈表

3.4 回文鏈表

3.5 小結

四雙鏈表

4.1 簡介 - 雙鏈表

4.1.1 定義

4.1.2 結點結構

4.1.3 操作

4.2 添加操作 - 雙鏈表

4.3 刪除操作 - 雙鏈表

五、小結 - 鏈表

5.1 小結

5.1.1 回顧

5.1.2 對照

5.2 合并兩個有序鏈表

5.3 兩數相加

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數據結構--鏈表(java)

一 簡介

1.1 結點結構

1.2 操作

1.3 添加操作 - 單鏈表

1.4 刪除操作 - 單鏈表

1.5 設計鏈表

二 雙指針技巧

2.1 給定一個鏈表，判斷鏈表中是否有環(huán)。

2.2 返回鏈表開始入環(huán)的第一個節(jié)點

2.3 相交鏈表

2.4 刪除鏈表的倒數第N個節(jié)點

2.5小結

2.5.1 提示

2.5.2 復雜度分析

三 經典問題

3.1 反轉鏈表

3.2 刪除鏈表中的節(jié)點

3.3 奇偶鏈表

3.4 回文鏈表

3.5 小結

四 雙鏈表

4.1 簡介 - 雙鏈表

4.1.1 定義

4.1.2 結點結構

4.1.3 操作

4.2 添加操作 - 雙鏈表

4.3 刪除操作 - 雙鏈表

五、小結 - 鏈表

5.1 小結

5.1.1 回顧

5.1.2 對照

5.2 合并兩個有序鏈表

5.3 兩數相加

參考

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一簡介

二雙指針技巧

2.1 給定一個鏈表，判斷鏈表中是否有環(huán)。

三經典問題

四雙鏈表

五、小結 - 鏈表