面試 8：快慢指針法玩轉連結清單算法面試（二）

昨天在最後給大家留了拓展題，不知道大家有沒有思考完成，其實南塵說有巨坑是吓大家的啦，實際上也沒什麼。我們來繼續看看昨天這個拓展題。

面試題：給定單連結清單的頭結點，删除單連結清單的倒數第 k 個結點。

前面的文章見連結：面試 7：面試常見的連結清單算法捷徑(一)

這個題和前面的文章中增加了一個操作，除了找出來這個結點，我們還要删除它。删除一個結點，想必大家必定也知道：要想操作（添加、删除）單連結清單的某個結點，那我們還得知道這個節點的前一個節點。是以我們要删除倒數第 k 個結點，就必須要找到倒數第 k+1 個結點。然後把倒數第 k+1 個元素的 next 變量 p.next 指向 p.next.next。

我們找到倒數第 k 個結點的時候，先讓 fast 走了 k-1 步，然後再讓 slow 變量和 fast 同步走，它們之間就會一直保持 k-1 的距離，是以當 fast 到連結清單尾結點的時候，slow 剛剛指向的是倒數第 k 個結點。

本題由于我們要知道倒數第 k+1 個結點，是以得讓 fast 先走 k 步，待 fast 指向連結清單尾結點的時候，slow 正好指向倒數第 k+1 個結點。

我們簡單思考一下臨界值：

1. 當 k = 1 的時候，删除的值是尾結點。我們讓 fast 先走 1 步，當 fast.next 為尾結點的時候，倒數第 k+1 個結點正好是我們的倒數第二個結點。我們删除 slow.next，并讓slow.next 指向 slow.next.next = null，滿足條件。
2. 當 k > len 的時候，我們要找的倒數第 k 個元素不存在，直接出錯；
3. 當 1 < k < len 的時候，k 最大為 len-1 的時候，fast 移動 len-1 步，直接到達尾結點，此時，snow 指向頭結點。删除倒數第 k 個元素，即删除正數第 2 個結點即可；
4. 當 k = len 的時候比較特殊，當 fast 移動 len 步的時候，已經指向了 fast.next = null，此時我們其實要删除的是頭結點，直接傳回 head.next 即可。

是以我們自然能得到這樣的代碼。

public class Test07 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static LinkNode delTheSpecifiedReverse(LinkNode head, int k) {
        LinkNode slow = head;
        LinkNode fast = head;
        if (fast == null) {
            throw new RuntimeException("your linkNode is null");
        }
        // 先讓 fast 先走 k 步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                // 說明輸入的 k 已經超過了連結清單長度，直接報錯
                throw new RuntimeException("the value k is too large.");
            }
            fast = fast.next;
        }
        // fast == null ，說明已經到了尾結點後面的空區域，說明要删除的就是頭結點。
        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        LinkNode node = delTheSpecifiedReverse(head, 3);
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
    }
}
           

好了，我們解決了昨天文章中留下的拓展題，今天我們來看看我們連結清單都還有些怎樣的考法。

面試題：定義一個單連結清單，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點。為了友善，我們連結清單的 data 采用整型。

這是一道反轉連結清單的經典題，我們來屢一下思路：一個結點包含下一結點的引用，反轉的意思就是要把原來指向下一結點的引用指向上一個結點。我們可以分為下面的步驟：

1. 找到目前要反轉的結點的下一個結點，并用變量儲存，因為下一次要反轉的是它，如果我們不儲存的話一定會因為前面已經反轉，導緻無法通過周遊得到這個結點；
2. 然後讓目前結點的 next 引用指向上一個結點，上一個結點初始 null 因為頭結點的反轉後變成尾結點；
3. 目前要反轉的結點變成下一個要比較元素的上一個結點，用變量儲存；
4. 目前要比較的結點指派為之前儲存的未反轉前的下一個結點；
5. 目前反轉的結點為 null 的時候，儲存的上一個結點即反轉後的連結清單頭結點。

用代碼實作就是：

public class Test08 {

    private static class LinkNode {
        int data;
        LinkNode next;

        LinkNode(int data) {
            this.data = data;
        }
    }

    private static LinkNode reverseLink(LinkNode head) {
        // 上一個結點
        LinkNode nodePre = null;
        LinkNode next = null;
        LinkNode node = head;
        while (node != null) {
            // 先用 next 儲存下一個要反轉的結點，不然會導緻連結清單斷裂。
            next = node.next;
            // 再把現在結點的 next 引用指向上一個結點
            node.next = nodePre;
            // 把目前結點指派給 nodePre 變量，以便于下一次指派
            nodePre = node;
            // 向後周遊
            node = next;
        }
        return nodePre;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        LinkNode node = reverseLink(head);
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
    }
}
           

連結清單可以考的可真多，相信不是小夥伴都和我一樣，雲裡霧裡了，那我們今天就講到這裡，後面還要繼續考算法，你，打起精神，别睡着了。