轉載請注明出處：http://www.itdecent.cn/p/c65d9d753c31

在上一篇博客《數(shù)據結構與算法（二），線性表》中介紹了線性表的創(chuàng)建、插入、刪除等基本操作，這一篇將總結一下鏈表中最?？嫉拿嬖囶}。

目錄：

• 1、從尾到頭打印單鏈表
• 2、在O(1)時間刪除鏈表結點
• 3、鏈表中倒數(shù)第k個結點
• 4、反轉鏈表
• 5、合并兩個有序鏈表
• 6、復雜鏈表的復制
• 6、兩個鏈表的第一個公共結點
• 7、判斷鏈表是否有環(huán)
• 8、求鏈表環(huán)的長度
• 9、鏈表中環(huán)的入口結點
• 10、刪除鏈表中重復的的結點

說明：為了測試方便，這里結點中存放數(shù)據的類型定義為int型。無特殊說明時，其結點結構為：

public class Node {
    int element;
    Node next;
    Node(int element) {
        this.element = element;
    }
}

另外在這篇文章中方法的輸入參數(shù)，head表示的是首元結點，不是頭結點。如，reversePrint(Node head)表示傳入的參數(shù)為首元結點。

1、從尾到頭打印單鏈表

題目：輸入一個鏈表的「頭結點」，從尾到頭反過來打印出每個結點的值。（劍指offer，第5題）

方法1：這里的頭結點，其實指的是首元結點，和鏈表創(chuàng)建時的頭結點不同，這點需要注意。從尾到頭打印單鏈表，也就是第一個結點最后一個打印，最后一個結點第一個打印，這是典型的「后進先出」。首先想到的是使用一個輔助棧，先將所有結點依次放入棧中，然后遍歷棧實現(xiàn)反轉打印。代碼如下：

//棧實現(xiàn)
public void reversePrint(Node head) {
    if(head == null) 
        return;
    Stack<Node> stack = new Stack<Node>();
    Node current = head;
    while(current != null) {
        stack.push(current);
        current = current.next;
    } 
    while(!stack.isEmpty()) {
      System.out.print(stack.pop().element + " ");       
    }
}

方法2：由于遞歸的本質就是一個棧結構，因此我們也可以使用遞歸來實現(xiàn)反轉打印。每次訪問一個結點時，先遞歸輸出它后面的結點，在輸出結點自身。代碼如下：

//遞歸實現(xiàn)
public void reversePrint(Node head) {
    if(head == null) 
        return;
    Node current = head;
    reversePrint(current.next);
    System.out.print(current.element + " ");
}

注意：

• 雖然遞歸實現(xiàn)代碼比較簡潔，但當鏈表非常長時，會導致調用棧溢出。而顯示使用棧來實現(xiàn)反轉打印不會出現(xiàn)這種問題，其魯棒性更好。
• reversePrint方法的輸入參數(shù)為首元結點，不是頭結點，調用這個方法時需注意。

2、在O(1)時間刪除鏈表結點

題目：給定單向鏈表的頭指針和一個結點指針，定義一個函數(shù)在 O(1)時間刪除該結點。（劍指offer，第13題）

這是一道經典的google面試題，一般來說要想刪除單向鏈表中的一個結點（current），必須要知道該結點前面一個結點（prior），然后使用prior.next = prior.next.next 方法來刪除該結點。但是單向鏈表中不能反向獲取前一個結點，只能通過順序遍歷鏈表來獲取，這時時間復雜度為 O(n)，明顯不符合要求。

其實換個思路，一個結點刪除自身很麻煩，刪除它的下一個結點（next）卻很簡單，只需要 O(1)的時間。我們只需將結點next的值覆賦給current（此時current原來的值被覆蓋），然后再刪除next即可。另外若current是尾結點則必須遍歷以獲取前一個結點。

public void deleteCurrent(Node head, Node current) {
    if(head == null || current == null) 
        return;

    if(current.next != null) { //current不是尾結點 
        current.element = current.next.element;
        current.next = current.next.next;
    }else if(head == current) { //只有一個結點，必須在current.next != null之后
        head = null;
        current = null;
    } else { //是尾節(jié)點
        Node node = head;
        while(node.next != current) {
            node = node.next;
        }
        node.next = null;
    }   
}

時間復雜度分析：

對于前 n-1 個結點其時間復雜度為 O(1)，尾結點其時間復雜度度為 O(n)，因此其平均時間復雜度為

另外需要注意，上述代碼基于一個假設：要刪除的結點在鏈表中。判斷一個結點是否在鏈表中需要 O(n) 的時間。受 O(1)的時間限制，我們把確保結點在鏈表中的責任推給了調用者。

3、鏈表中倒數(shù)第k個結點

題目：輸入一個鏈表，輸出該鏈表中倒數(shù)第 k 個結點。如：一個鏈表為 1 -> 2 ->3 -> 4 -> 5 -> 6，其倒數(shù)第3個結點為 4。（劍指offer，第15題）

若整個鏈表有n個結點，那么倒數(shù)第k個結點就是從頭結點開始的第n-k+1個結點，只需遍歷一次鏈表找到這個結點即可。幸運的是在上一篇《數(shù)據結構與算法（二），線性表》中創(chuàng)建的鏈表能夠通過size( )方法在 O(1)時間獲取鏈表的長度。但有時鏈表是以首元結點的形式給出的，這時我們就需要首先遍歷一次鏈表以獲取其長度，然后才能運用上面的方法。也就是說需要遍歷兩次鏈表，第一次統(tǒng)計結點個數(shù)，第二次查找第n-k+1個結點。

一種改進方法是定義兩個指針，從鏈表首元結點開始第一個指針先向前走 k-1 步，然后兩個指針一起向前遍歷，直到第一個指針到達鏈表的尾結點，此時第二個指針所指的結點即為所求。這里注意以下情況需要進行特殊處理：

• 鏈表結點總數(shù)小于k
• k為0
• 鏈表為null

代碼如下：

public Node findKthToTail(Node head, int k) {
    if(head == null || k == 0)
        return null;
    Node aNode = head;
    for (int i=0; i<k-1 ; i++ ) {
        if(aNode.next == null) {
            return null;
        }
        aNode = aNode.next;
    }
    Node bNode = head;
    while(aNode.next != null) { //尾結點不為空
        aNode = aNode.next;
        bNode = bNode.next;
    }
    return bNode;
}

4、反轉鏈表

題目：定義一個函數(shù)，輸入一個鏈表的頭結點，反轉該鏈表并輸出反轉后鏈表的頭結點。如：一個鏈表為 1 -> 2 ->3 -> 4 -> 5 -> 6，其反轉鏈表為 6 -> 5 -> 4 -> 3 -> 2 -> 1。（劍指offer，第16題）

方法1：借助于棧的先進后出的特點反轉鏈表，具體做法是先將鏈表的結點按順序依次入棧，然后再依次出棧并鏈接在一起，最后返回首元結點的引用

// 鏈表反轉,借助于棧實現(xiàn)
public Node reverseList(Node head) { 
    if(head == null || head.next == null) //鏈表為空或只有一個元素，無需反轉
        return head;      
    Stack<Node> stack = new Stack<Node>();
    Node current = head;
    while(current != null) {
        stack.push(current);
        current = current.next;
    }
    Node reverse = stack.pop();
    current = reverse;
    while(!stack.isEmpty()) {
        current.next = stack.pop();
        current = current.next;
    }
    current.next = null; //【防止形成循環(huán)鏈表】
    return reverse;
}

方法2：遞歸實現(xiàn)，我們假設鏈表最后N-1個結點已經完成反轉，則此時鏈表的狀態(tài)如下圖，現(xiàn)在只需將current插入到結果鏈表的末端。 注意：最后一定要加上current.next = null否則將出現(xiàn)環(huán)。

代碼實現(xiàn)：

//鏈表反轉,遞歸實現(xiàn)(注意遞歸的地方)
public Node reverseList(Node head) {
    if(head == null || head.next == null) 
        return head;
    Node current = head;
    Node reverse = reverseList(current.next);
    current.next.next = current;
    current.next = null; // 防止出現(xiàn)環(huán)
    return reverse;
}

方法3：迭代實現(xiàn)（最優(yōu)）。需要三個引用，如下圖所示，aNode指向反轉后鏈表的首結點，bNode指向原鏈表中剩余結點的首結點，cNode指向原鏈表中剩余結點的第二個結點。在每輪迭代中，將bNode插入到逆鏈表的開頭。

代碼如下：

//鏈表反轉,迭代實現(xiàn)
public Node reverseList(Node head) {
    Node aNode = null;
    Node bNode = head;
    Node cNode = null;
    while(bNode != null) {
        cNode = bNode.next;
        bNode.next = aNode;
        aNode = bNode;
        bNode = cNode;
    }
    return aNode;
}

5、合并兩個有序鏈表

題目：輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的結點仍按遞增排序。(劍指offer，第17題）。如：

鏈表a： 1 -> 3 -> 5 ->7

鏈表b： 2 -> 4 -> 6 ->8

合并后： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

方法1：遞歸實現(xiàn)，兩個鏈表的初始狀態(tài)如下圖，首先比較兩個鏈表的首結點，將較小的首結點鏈接到「已經合并的鏈表」之后，此時兩個鏈表剩下的部分依然有序，可以遞歸調用函數(shù)合并鏈表。注意：兩個鏈表為空的情況。

合并鏈表

代碼如下：

public Node merge(Node aHead, Node bHead) {
    if(aHead == null) 
        return bHead;
    if(bHead == null)
        return aHead;
    Node mergeHead = null;
    if(aHead.element > bHead.element) {
        mergeHead = bHead;
        mergeHead.next = merge(aHead, bHead.next);
    }else {
        mergeHead = aHead;
        mergeHead.next = merge(aHead.next, bHead);
    }
    return mergeHead;
}

方法2：遞歸的方法可能比較難理解，這里給出一種直接的解法。首先比較兩個鏈表的首結點，獲取合并后鏈表的首結點，然后依次比較剩下部分的首結點，直到一個鏈表為空，最后將不為空的鏈表鏈接到「已經合并的鏈表」之后。

public Node merge(Node aHead, Node bHead) {
    if(aHead == null) 
        return bHead;
    if(bHead == null)
        return aHead;

    //求合并后鏈表的首結點
    Node mergeHead = null;
    Node current = null;
    if(aHead.element > bHead.element) {
        mergeHead = bHead;
        bHead = bHead.next;
    }else {
        mergeHead = aHead;
        aHead = aHead.next;
    }

    current = mergeHead;
    while(aHead != null && bHead != null) {
        if(aHead.element > bHead.element) {
            current.next = bHead;
            bHead = bHead.next;
        }else {
            current.next = aHead;
            aHead = aHead.next;
        }
        current = current.next;
    }

    //合并剩余部分
    if(aHead == null) { //a鏈表為空，
        current.next = bHead;
    }else { //b為空
        current.next = aHead;
    }
    return mergeHead;   
}

6、復雜鏈表的復制

題目：復制一個復雜鏈表，在復雜鏈表中，每個結點除了有一個指針指向下一個結點外，還有一個指針指向鏈表中的任意結點或NULL。（劍指offer，第26題）

復雜鏈表中的結點結構：

public class ComplexNode() {
    int element;
    ComplexNode next;
    ComplexNode random;
}

方法1：直接復制，首先復制原始鏈表中每個結點，并使用next指針鏈接起來；然后再遍歷原始鏈表，設置每個結點的random指針。若當前結點C的random域指向結點S，由于S可能位于C的前面也可能位于C的后面，所以為了確定S的在鏈表中的位置，每次都需從頭開始遍歷鏈表。

public ComplexNode cloneComplexList(ComplexNode pHead){
    //鏈表為空或只有一個元素
    if(pHead == null) 
        return pHead;
    if(pHead.next == null) 
        return new ComplexNode(pHead.element);

    //復制原始鏈表
    ComplexNode cloneHead = new ComplexNode(pHead.element);
    ComplexNode cloneCurrent = cloneHead;
    ComplexNode pCurrent = pHead;
    while(pCurrent.next != null) {
        
        cloneCurrent.next = new ComplexNode(pCurrent.next.element); 
        cloneCurrent = cloneCurrent.next;
        pCurrent = pCurrent.next;
    }
    //復制random域
    pCurrent = pHead;
    cloneCurrent = cloneHead;
    while(pCurrent != null) {
        if(pCurrent.random != null) {
            //定位random指向的位置
            int index = 0;
            ComplexNode temp = pHead;
            while(temp != pCurrent.random) {
                index++;
                temp = temp.next;
            }
            temp = cloneHead;
            while(index != 0) {
                index--;
                temp = temp.next;
            }
            cloneCurrent.random = temp;
        }
        pCurrent = pCurrent.next;
        cloneCurrent = cloneCurrent.next;
    }    
    return cloneHead;
}

由于定位每個結點的random都需從頭開始遍歷鏈表，因此此方法的時間復雜度為 O(n^2)。

方法2：利用哈希表，由于方法1的主要時間花費在了定位結點的random上，我們可以利用哈希表建立原鏈表結點與復制后鏈表結點的對應關系，這樣就可以在O(1)的時間找到random。

public ComplexNode cloneComplexList(ComplexNode pHead){
    //鏈表為空或只有一個元素
    if(pHead == null) 
        return pHead;
    if(pHead.next == null) 
        return new ComplexNode(pHead.element);

    //復制原始鏈表
    Map<ComplexNode, ComplexNode> map = new HashMap<>();
    ComplexNode cloneHead = new ComplexNode(pHead.element);
    ComplexNode cloneCurrent = cloneHead;
    ComplexNode pCurrent = pHead;
    map.put(pCurrent, cloneCurrent);
    while(pCurrent.next != null) {       
        cloneCurrent.next = new ComplexNode(pCurrent.next.element); 
        cloneCurrent = cloneCurrent.next;
        pCurrent = pCurrent.next;
        map.put(pCurrent, cloneCurrent);
    }
    //復制random域
    pCurrent = pHead;
    cloneCurrent = cloneHead;
    while(pCurrent != null) {
        if(pCurrent.random != null) {
            cloneCurrent.random = map.get(pCurrent.random); // O(1)
        }
        pCurrent = pCurrent.next;
        cloneCurrent = cloneCurrent.next;
    }    
    return cloneHead;
}

此方法相當于用空間換時間，使用大小為O(n)的哈希表，將時間復雜度由O(n^2)降為 O(n)。

方法3：不用輔助空間

• 第一步，復制原鏈表中的每個結點，若N的復制結點為N'，并將N'插入到N的后面組成一個長鏈表；
• 第二步，若原鏈表中結點N的random指向結點S，則復制結點N'指向結點S'（S的復制結點），設置復制結點的random域；
• 第三步，將長鏈表拆分為兩個鏈表，奇數(shù)位置的結點鏈接為原鏈表，偶數(shù)位置的結點鏈接為復制的鏈表。

其復制過程如下：

復雜鏈表的復制過程

代碼如下：

public ComplexNode cloneComplexList(ComplexNode pHead){
    if(pHead == null) 
        return pHead;
    if(pHead.next == null) 
        return new ComplexNode(pHead.element);

    //第一步
    ComplexNode pCurrent = pHead;
    ComplexNode temp;
    while(pCurrent != null) {           
        temp = new ComplexNode(pCurrent.element);
        temp.next = pCurrent.next;
        pCurrent.next = temp;
        pCurrent = pCurrent.next.next;
    }
    
    //第二步，復制random域
    pCurrent = pHead;
    while(pCurrent != null) {
        if(pCurrent.random != null) {
            pCurrent.next.random = pCurrent.random.next;
        }
        pCurrent = pCurrent.next.next;
    }
         
    //第三步，拆分長鏈表
    ComplexNode cloneHead = pHead.next;
    ComplexNode cloneCurrent = cloneHead;
    pCurrent = pHead;
    pCurrent.next = cloneCurrent.next; //從長鏈表中刪除復制的結點，
    pCurrent = pCurrent.next;
    while(pCurrent != null) {
        cloneCurrent.next = pCurrent.next;
        cloneCurrent = cloneCurrent.next;
        pCurrent.next = cloneCurrent.next; //從長鏈表中刪除復制的結點，【關鍵】
        pCurrent = pCurrent.next;
        
    }        
    return cloneHead;
}

注意：拆分鏈表時，不但要拆分出復制后的鏈表，還要將原鏈表還原。方法3是通過將長鏈表中的復制結點刪除的方法來還原原鏈表的。

6、兩個鏈表的第一個公共結點

題目：輸入兩個鏈表，找到它們的第一個公共結點。其可能的結構有：

兩個鏈表的結構

方法1：暴力方法，在第一條鏈表上順序遍歷每個結點，每遍歷到一個結點就遍歷第二條鏈表，看在第二條鏈表上是否有結點與其相同。

public Node findFirstCommonNode(Node head1, Node head2) {
        
    Node current1 = head1;        
    while(current1 != null) {
        Node current2 = head2;
        while(current2 != null) {
            if(current1 == current2)
                return current1;
            current2 = current2.next;
        }
        current1 = current1.next;
    }
    return null;
}

顯然，若兩鏈表長度分別為m、n，則此算法的時間復雜度為 O(m*n)。

方法2：利用棧，從前面的圖可以看出，若兩鏈表有公共結點，則從第一個公共結點開始，之后它們的所有結點都重合，。若從鏈表的尾部開始向前比較，則最后一個相同的結點即為第一個公共結點?！负筮M先出」

代碼如下：

public Node findFirstCommonNode(Node head1, Node head2) {
        
    Stack<Node> stack1 = addToStack(head1);
    Stack<Node> stack2 = addToStack(head2);

    Node lastNode = null; 
    while(!stack1.isEmpty() && !stack2.isEmpty()) {
        lastNode = stack1.pop();
        if(lastNode != stack2.pop()) {
            return lastNode.next;  //Y型結構，結構1，結構4
        }
    }
    //結構2,3
    if(stack1.isEmpty())
        return head1;
    if(stack2.isEmpty())
        return head2;

    //好像不會執(zhí)行到？
    return null; 
}

private Stack<Node> addToStack(Node head) {
    Node current = head;        
    Stack<Node> stack = new Stack<>();
    while(current != null) {
        stack.push(current);
        current = current.next;
    }
    return stack;
}

此算法的時間復雜度與空間復雜度都為 O(m + n)?！赣每臻g換時間」。

方法3:最常用的方法，首先遍歷兩個鏈表得到它們的長度L1、L2（不妨設L1 > L2)，然后較長的鏈表先走（L1 - L2）步，接著再同時遍歷兩鏈表，找到的第一個相同的結點即為所求。

public Node findFirstCommonNode(Node head1, Node head2) {
    int len1 = getLength(head1);
    int len2 = getLength(head2);
    Node current1 = head1;
    Node current2 = head2;
    if(len1 >= len2) {
        for(int i=0; i<len1-len2; i++) {
            current1 = current1.next;
        }
    }else {
       for(int i=0; i<len2-len1; i++) {
            current2 = current2.next;
        } 
    }
    while(current1 != null) {
        if(current1 == current2) 
            return current1;
        current1 = current1.next;
        current2 = current2.next;
    }
    return null;
}

private int getLength(Node head) {
    Node current = head;
    int i = 0;
    while(current != null) {
        i++;
        current = current.next;
    }
    return i;
}

此方法時間復雜度為O(m + n)，并且不再需要輔助棧，因此提高了空間效率。

方法4：最簡潔，也最難理解的方法。。廢話不多說，先上代碼。

public Node findFirstCommonNode(Node head1, Node head2) {
    Node p1 = head1;
    Node p2 = head2;
    while(p1 != p2) {
        p1 = (p1 == null ? head2 : p1.next);
        p2 = (p2 == null ? head1 : p2.next);
    }
    return p1;
}

兩個指針p1、p2每次走一步，若兩鏈表長度相同，

• 若有公共結點，遍歷到公共結點時p1 = p2返回；
• 若無公共結點，遍歷到尾部NULL時p1 = p2，返回NULL

若兩鏈表長度不同，指向短鏈表指針先走完，然后指向長鏈表，指向長鏈表指針后走完，然后指向短鏈表。此時等效為長度相同，如下圖

• 過程同上面「兩鏈表長度相同時」

此算法的時間復雜度同樣為 O(m + n)

7、判斷鏈表是否有環(huán)

題目：一個鏈表，判斷其是否又環(huán)。

如果一個鏈表有環(huán)，那么用一個指針遍歷將永遠也走不到盡頭。使用兩個指針遍歷：first每次走一步，second每次走兩步。若鏈表有環(huán)則它們一定會相遇。

代碼如下：

//判斷鏈表是否有環(huán)
public boolean hasLoop(Node head) {
    Node first = head;
    Node second = head;
    //【判斷條件second在前，second.next在后，否則可能會報空指針異常】
    while(second != null && second.next != null  ) {
        first = first.next;
        second = second.next.next;
        if(first == second)
            return true;
    }
    return false;
}

8、求鏈表環(huán)的長度

題目：一個鏈表，求其環(huán)的長度。

若鏈表無環(huán)，則其長度為0；若鏈表有環(huán)，則second和first指針相遇時，相遇點一定在環(huán)中。記錄下相遇點，first再次走到該點時走到長度即為所求。

//得到相遇點
private Node getMeetNode(Node head) {
    Node first = head;
    Node second = head;
    //【判斷條件second在前，second.next在后，否則可能會報空指針異?！?    while(second != null && second.next != null  ) {
        first = first.next;
        second = second.next.next;
        if(first == second)
            return first;
    }
    return null;
}

public int getLoopLength(Node head) {

    Node meetNode = getMeetNode(head);
    if(meetNode == null) //無環(huán)
        return 0;
    Node first = meetNode.next;
    int result = 1;
    while(first != meetNode) {
        result++;
        first = first.next;
    }
    return result;
}

9、鏈表中環(huán)的入口結點

題目：一個鏈表中包含環(huán)，請找出該鏈表的環(huán)的入口結點。（劍指offer，第56題）

方法1：若知道環(huán)的長度 len （第8題已求），定義兩個指針first、second，讓first先走 len 步，然后first和second一起向前走，兩者必然會相遇，相遇點即為環(huán)的入口結點。

//getLoopLength方法見第8題

public Node entryNodeOfLoop(Node head){
    
    Node first = head;
    Node second = head;
    int len = getLoopLength(head);
    if(len == 0)
        return null;
    for(int i=0; i<len; i++) {
        first = first.next;
    }
    while(first != null) {
        if(first == second) {
            return first;
        }
        first = first.next;
        second = second.next;
    }
    return null;
}

方法2：借助于HashMap或HashSet，遍歷鏈表，遇到第一個已遍歷過的結點即為環(huán)的入口結點。

//借助于set
public Node entryNodeOfLoop(Node head) {
    Set<Node> set = new HashSet<>(); 
    Node current = head;
    while(current != null) {
        if(!set.add(current)) {
            return current;
        }
        current = current.next;
    }
    return null;
}

//或者借助于map
public Node entryNodeOfLoop(Node head){
    Map<Node, Boolean> map = new HashMap<>();
    Node current = head;
    while(current != null) {
        if(map.containsKey(current)) {
            return current;
        }
        map.put(current, true);
        current = current.next;
    }
    return null;
}

10、刪除鏈表中重復的的結點

題目：在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5 。（劍指offer，第57題）

請注意，這里鏈表是排好序的。

代碼如下：

public Node deleteDuplication(Node head){
    if(head==null || head.next==null) 
        return head;

    Node current = head;        
    if(current.val!=current.next.val){
        current.next = deleteDuplication(current.next);
        return current;
    }else {
        int val = current.val;
        while(current.val==val){
            current = current.next;
            if(current==null) 
                return null;
        }
        return deleteDuplication(current);
    }  
}

好了，就先總結到這里吧。將來找工作刷題時，再來補充。