摘要：概述前面的文章說到了一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)鏈表數(shù)據(jù)結(jié)構(gòu)與算法鏈表，今天就來看看關(guān)于單鏈表的幾種常見的操作，技術(shù)筆試的時(shí)候很大概率能夠遇到其中的一些。

1. 概述

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

單鏈表反轉(zhuǎn)

合并兩個(gè)有序鏈表

檢測鏈表中的環(huán)

刪除鏈表倒數(shù)第 k 個(gè)節(jié)點(diǎn)

找到鏈表的中間節(jié)點(diǎn)

2. 單鏈表反轉(zhuǎn)

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

public class SingleLinkedList {
    private Node head = null;//鏈表的頭節(jié)點(diǎn)
    
    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. 合并兩個(gè)有序鏈表

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

    //合并兩個(gè)有序的鏈表
    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;
        
        //比較第一個(gè)元素
        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. 檢測鏈表中的環(huán)

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

    //檢測鏈表中的環(huán)
    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. 刪除鏈表倒數(shù)第 k 個(gè)節(jié)點(diǎn)

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

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;
        //前后指針同時(shí)移動
        while(fast.next != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        
        if(prev == null) {//說明刪除的是第一個(gè)節(jié)點(diǎn)
            head = head.next;
        }else {
            prev.next = prev.next.next;
        }
        
        return head;
    }

6. 找到鏈表的中間節(jié)點(diǎn)

尋找鏈表中間的那個(gè)節(jié)點(diǎn)，思路很簡單，也是定義兩個(gè)指針，一個(gè)指針每次移動兩個(gè)節(jié)點(diǎn)，另一個(gè)指針移動一個(gè)節(jié)點(diǎn)，前面的指針到達(dá)鏈表尾部的時(shí)候，后面的指針指向的節(jié)點(diǎn)就是中間的那個(gè)節(jié)點(diǎn)：

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;
    }