xwzz.jpg

重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 開(kāi)篇
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(二)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 數(shù)組
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 鏈表(一)

前章，介紹了常見(jiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)有：

• 單向鏈表
• 循環(huán)鏈表
• 雙向鏈表
• 雙向循環(huán)鏈表

本章主要做幾道練習(xí)題來(lái)加深對(duì)鏈表數(shù)據(jù)結(jié)構(gòu)印象，每題都需考慮以下邊界問(wèn)題：

• 如果鏈表為空時(shí)，代碼是否能正常工作？
• 如果鏈表只包含一個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 如果鏈表只包含兩個(gè)結(jié)點(diǎn)時(shí)，代碼是否能正常工作？
• 代碼邏輯在處理頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)候，是否能正常工作？

練習(xí)1：?jiǎn)蜗蜴湵矸崔D(zhuǎn)

反轉(zhuǎn)前.png

如何將已知的單向鏈表反轉(zhuǎn)？

反轉(zhuǎn)后.png

思路：遍歷所有結(jié)點(diǎn)，將當(dāng)前結(jié)點(diǎn)的next指針指向前結(jié)點(diǎn)，操作完成后原尾結(jié)點(diǎn)作為首結(jié)點(diǎn)即可。

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

 public static Node reverseNode(Node first) {
    if (first == null) return null;
    if (first.next == null) return first;

    // 從首結(jié)點(diǎn)開(kāi)始，首結(jié)點(diǎn)的上結(jié)點(diǎn)為空結(jié)點(diǎn)
    Node curNode = first;
    Node preNode = null;

    while (curNode != null) {
        Node tempNext = curNode.next;   // 暫存當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)

        curNode.next = preNode;     // 讓當(dāng)前結(jié)點(diǎn)指向上一結(jié)點(diǎn)

        // 切換到下一結(jié)點(diǎn)
        preNode = curNode;
        curNode = tempNext;
    }

    return preNode; //循環(huán)結(jié)束，上一結(jié)點(diǎn)就是首結(jié)點(diǎn)
}

測(cè)試：

// 測(cè)試數(shù)據(jù)
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
// 測(cè)試代碼
printAll(node1);
Node result = reverseNode(node1);
printAll(result);

輸出：

1 2 3 4 5  // 反轉(zhuǎn)前
5 4 3 2 1  // 反轉(zhuǎn)后

練習(xí)2：循環(huán)鏈表檢測(cè)

給你一個(gè)任意鏈表結(jié)點(diǎn)，如何校驗(yàn)其是否是循環(huán)鏈表？

思路： 通過(guò)快、慢指針同時(shí)遍歷鏈表，快指針步長(zhǎng)為2，慢指針步長(zhǎng)為1，當(dāng)快指針追上慢指針就是循環(huán)鏈表，否則快指針遍歷到尾結(jié)點(diǎn)（next->null）就非循環(huán)鏈表。
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

/**
 * 檢測(cè)鏈表是否是循環(huán)鏈表
 * */
public static boolean checkCircleNode(Node first) {
    if (first == null) return false;
    Node fast = first.next;
    Node slow = first;
    while (fast != null && fast.next != null) {
        if (fast == slow) return true;
        fast = fast.next.next;  // 快指針走兩步
        slow = slow.next;       // 慢指針走一步
    }
    return false;
}

測(cè)試：

    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    node1.next = node2;
    node2.next = node3;
    node3.next = node1;
    System.out.println(checkCircleNode(node1));

    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node4.next = node5;
    node5.next = null;
    System.out.println(checkCircleNode(node4));

    Node node6 = new Node(6);
    System.out.println(checkCircleNode(node6));

    Node node7 = new Node(7);
    node7.next = node7;
    System.out.println(checkCircle(node7));

    System.out.println(checkCircleNode(null));

輸出：

true
false
false
true
false

練習(xí)3：合并有序鏈表

如何將兩個(gè)從小到大的有序鏈表合并為一個(gè)有序鏈表？例如：

• 鏈表1 : [ 1 , 3 , 5 , 7 , 9 ]
• 鏈表2 : [ 2 , 4 , 6 , 8 , 10]
• 合并后鏈表：[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]

思路：
1、比較兩者首結(jié)點(diǎn)、以最小結(jié)點(diǎn)作為合并鏈表的首結(jié)點(diǎn)
2、定義兩個(gè)指針p,q，分別指向這兩鏈表首結(jié)點(diǎn)，定義一個(gè)臨時(shí)指針temp指向合并鏈表的首結(jié)點(diǎn)
3、同時(shí)開(kāi)始遍歷兩個(gè)鏈表，如果有一個(gè)鏈表先到達(dá)尾部，則停止遍歷
4、遍歷中，取p、q指針數(shù)據(jù)的較小者鏈接到合并鏈表的尾部
5、遍歷結(jié)束，temp拼接p鏈表或者q鏈表剩余結(jié)點(diǎn)（兩鏈表長(zhǎng)度可能不等）
6、返回合并鏈表首結(jié)點(diǎn)
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

public static Node mergeSortedNode(Node list1, Node list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    // p,q 指針?lè)謩e指向 鏈表1、鏈表2
    Node p = list1;
    Node q = list2;

    // 確認(rèn)合并鏈表的首結(jié)點(diǎn)
    Node head;
    if (p.data <= q.data) {
        head = p;
        p = p.next;
    } else {
        head = q;
        q = q.next;
    }

    //開(kāi)始遍歷排序
    Node tempNode = head;
    while (p != null && q != null) {
        // 取小值鏈接到合并鏈表尾部
        if (p.data <= q.data) {
            tempNode.next = p;
            p = p.next;
        } else {
            tempNode.next = q;
            q = q.next;
        }
        // 開(kāi)啟下一輪
        tempNode = tempNode.next;
    }

    // 拼接剩余尾部
    if (p == null) {
        tempNode.next = q;
    } else {
        tempNode.next = p;
    }
    return head;
}

測(cè)試：

// 測(cè)試數(shù)據(jù)1
public static Node getNodeList1() {
    Node node1 = new Node(1);
    Node node2 = new Node(3);
    Node node3 = new Node(5);
    Node node4 = new Node(7);
    Node node5 = new Node(9);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}
// 測(cè)試數(shù)據(jù)2
public static Node getNodeList2() {
    Node node1 = new Node(2);
    Node node2 = new Node(4);
    Node node3 = new Node(6);
    Node node4 = new Node(8);
    Node node5 = new Node(10);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}
// 測(cè)試代碼
private static void test() {
    Node list1 = getNodeList1();
    list1.print();

    Node list2 = getNodeList2();
    list2.print();

    Node mergeNode = mergeSortedNode(list1, list2);
    mergeNode.print();
}

輸出：

1   3   5   7   9
2   4   6   8   10
1   2   3   4   5   6   7   8   9   10

練習(xí)4：刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)

思路：如何定位到倒數(shù)第n結(jié)點(diǎn)？

1、定義快指針，指向正數(shù)第n結(jié)點(diǎn)；
2、再定義慢指針指向首結(jié)點(diǎn)；
3、快慢指針同時(shí)以步長(zhǎng)1開(kāi)始遍歷鏈表，當(dāng)快指針到達(dá)尾結(jié)點(diǎn)時(shí)，慢指針正好停留在倒數(shù)第n結(jié)點(diǎn)；
4、考慮到單鏈表刪除，需要知道前結(jié)點(diǎn)，所以在第3步遍歷前定義pre指針指向慢指針的前結(jié)點(diǎn)；
5、當(dāng)遍歷完成可能出現(xiàn)兩種情況：

• 情況1：pre指向結(jié)點(diǎn)不為null，刪除慢指針結(jié)點(diǎn)即可；
• 情況2：pre指向null，此時(shí)要?jiǎng)h除的正好是首結(jié)點(diǎn)。
  時(shí)間復(fù)雜度：O(n)
  空間復(fù)雜度：O(1)

 public static Node deleteLastTh(Node list, int n) {
    if (list == null || n < 1) return list;

    Node fast = list;
    int i = 1;
    while (fast != null && i < n) {
        fast = fast.next;
        i++;
    }
    //不存在倒數(shù)第n個(gè)結(jié)點(diǎn)
    if (fast == null) return list;

    //開(kāi)始運(yùn)算，定位倒數(shù)n結(jié)點(diǎn)
    Node slow = list;
    Node pre = null;
    while (fast.next != null) {
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }

    if (pre == null) {
        //倒數(shù)n結(jié)點(diǎn)正好是首結(jié)點(diǎn)
        list = list.next;
    } else {
        //循環(huán)結(jié)束，slow就為倒數(shù)第n個(gè)結(jié)點(diǎn)，操作pre結(jié)點(diǎn)刪除slow結(jié)點(diǎn)
        pre.next = pre.next.next;
    }
    return list;
}

測(cè)試：

    //測(cè)試數(shù)據(jù)
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;

    //測(cè)試代碼
    node1.print();
    Node node = deleteLastTh(node1, 3);
    node.print();

輸出：

1   2   3   4   5
1   2   4   5

練習(xí)5：求鏈表的中間結(jié)點(diǎn)

思路：
1、定義快慢指針同時(shí)遍歷鏈表，快指針步長(zhǎng)為2，慢指針步長(zhǎng)為1
2、當(dāng)快指針到達(dá)尾結(jié)點(diǎn)，慢指針正好在中心結(jié)點(diǎn)
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

public static Node findMiddleNode(Node list) {
    if (list == null) return null;
    Node slow = list;
    Node fast = list;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;       // 步長(zhǎng)1：慢指針
        fast = fast.next.next;  // 步長(zhǎng)2：快指針
    }
    return slow;
}

測(cè)試：

    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;

    node1.print();
    Node middleNode = findMiddleNode(node1);
    System.out.println(middleNode.data);

輸出：

1   2   3   4   5
3