摘要：概述前面的文章說到了一種很基礎的數據結構鏈表數據結構與算法鏈表，今天就來看看關于單鏈表的幾種常見的操作，技術筆試的時候很大概率能夠遇到其中的一些。

1. 概述

前面的文章說到了一種很基礎的數據結構——鏈表：數據結構與算法——鏈表，今天就來看看關于單鏈表的幾種常見的操作，技術筆試的時候很大概率能夠遇到其中的一些。多練習一下，對我們理解鏈表有很大的幫助，也能夠提升我們的編碼能力。
廢話不多說，這幾個練習題是：

單鏈表反轉

合并兩個有序鏈表

檢測鏈表中的環

刪除鏈表倒數第 k 個節點

找到鏈表的中間節點

2. 單鏈表反轉

單鏈表反轉，顧名思義，就是將鏈表的指針指向全部倒過來，尾結點變成頭節點，頭節點變成尾結點。具體的代碼如下：

public class SingleLinkedList {
    private Node head = null;//鏈表的頭節點
    
    public Node reverse(Node node) {
        Node head = null;
        Node previous = null;
        Node current = node;
        
        while(current != null) {
            Node next = current.next; 
            if (next == null) {
                head = current;
            }
            current.next = previous;
            previous = current;
            current = next;
        }
        
        this.head = head;
        return this.head;
    }
}

3. 合并兩個有序鏈表

假如鏈表中存儲的數據是數值類型，并且是有序的，這時候可以合并兩個有序的鏈表，主要涉及到兩個鏈表元素的比較。代碼如下：

    //合并兩個有序的鏈表
    public Node mergeSortedList(Node la, Node lb) {
        if(la == null && lb == null) return null;
        if(la == null) return lb;
        if(lb == null) return la;
        
        Node p = la;
        Node q = lb;
        Node head = null;
        
        //比較第一個元素
        if(p.getData() < q.getData()) {
            head = p;
            p = p.next;
        }else {
            head = q;
            q = q.next;
        }
        
        //比較后面的元素
        Node r = head;
        while(p != null && q != null) {
            if(p.getData() < q.getData()) {
                r.next = p;
                p = p.next;
            }else {
                r.next = q;
                q = q.next;
            }
            r = r.next;
        }
        
        //比較鏈表可能剩余的元素
        while(p != null) {
            r.next = p;
            p = p.next;
            r = r.next;
        }
        while(q != null) {
            r.next = q;
            q = q.next;
            r = r.next;
        }
        
        return head;
    }

4. 檢測鏈表中的環

單鏈表中有可能存在像循環鏈表這樣的環形結構，檢測鏈表中是否有這樣的結構，可以利用這樣的思路：定義兩個指針，一個指針每次移動兩個節點，另一個指針移動一個節點，如果兩個指針相遇，則說明存在環，代碼如下：

    //檢測鏈表中的環
    public boolean checkCircle(Node node) {
        if(node == null) return false;
        
        Node fast = node.next;
        Node slow = node;
    
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow) return true;
        }
        
        return false;
    }

5. 刪除鏈表倒數第 k 個節點

這個題在筆試當中非常常見，解決的思路比較的巧妙，不容易想到，但是只要一想到，代碼寫起來就很簡單了。主要的思路是這樣的：定義一個指針 fast，從鏈表頭開始，移動 k-1 個節點，再定義一個指針 slow，同時移動 fast 和 slow ，當 fast 到達鏈表尾節點的時候，slow 所指向的節點就是要刪除的節點。
具體的代碼實現如下：

public static Node deleteLastKth(Node head, int k) {
        Node fast = head;
        int i = 1;
        //先讓前面的指針移動k - 1步
        while(fast != null && i < k) {
            fast = fast.next;
            ++ i;
        }
        
        Node slow = head;
        Node prev = null;
        //前后指針同時移動
        while(fast.next != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        
        if(prev == null) {//說明刪除的是第一個節點
            head = head.next;
        }else {
            prev.next = prev.next.next;
        }
        
        return head;
    }

6. 找到鏈表的中間節點

尋找鏈表中間的那個節點，思路很簡單，也是定義兩個指針，一個指針每次移動兩個節點，另一個指針移動一個節點，前面的指針到達鏈表尾部的時候，后面的指針指向的節點就是中間的那個節點：

public static Node findMiddleNode(Node head) {
        if(head == null) return null;
        
        Node fast = head;
        Node slow = head;
        
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }