0.概述

本文主要討論鏈表在面試筆試中的題目，內容比較基礎，但在論壇上的面經中出現的頻率很高，也是做更困難鏈表題目的基礎。

0.1鏈表的數據結構

單鏈表

class Node<V> {
    V value;
    Node next;
    
    public Node(V value){
        this.value = value;
    }
}

雙向鏈表

class DoubleNode<V> {
    V value;
    DoubleNode last;
    DoubleNode next;
    
    public Node(V value){
        this.value = value;
    }
}

1.鏈表反轉

基礎博文主要包括兩個題目，反轉單向鏈表，反轉雙向鏈表；基礎題目，不做過多分析解釋，看註釋就能看明白。

1.1 單鏈表反轉

public static Node reverseList(Node head) {
    //指針變數，pre表示操作節點的前一個節點，初始都未null，next爲操作節點的後一個節點
    Node pre = null;
    Node next;

    while(head != null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }

    return pre;
}

1.2 雙向鏈表反轉

public static DoubleNode reverseDoubleList(DoubleNode head) {
    //指針變數，next爲操作節點的後一個節點,
    Node next;

    //實現思路比單向還要簡單，就是把每個節點的last和next節點互換就可以了
    while(head.next != null){
        next = head.next;
        head.next = head.last;
        head.last = next;
        head = next;
    }

    //上述while回圈到最後一個節點結束，head節點爲最後一個節點，但此時還不能返回head，因爲它還沒把上下節點互換
    head.next = head.last;
    head.last = null;

    return head;
}

2.列印兩個有序鏈表的公共部分

題目：

有兩個排好序的單鏈表，列印出兩個鏈表的共同節點；比如：
兩鏈表：1->2->3->7->null;
2->7->9->null;
結果： 2，7

分析：

最簡單的方式，把一個鏈表全部放到有序表中，然後遍歷另一個鏈表，檢查是否在有序表中出現，這也是做判斷某個元素是否在某個集閤中出現的常用做法。

public class Solution{
    public static void printCommonPart1(Node head1, Node head2){

        HashSet<Integer> sites = new HashSet<>();
        Node temp1 = head1;
        Node temp2 = head2;

        while(temp1 != null) {
            sites.add(temp1.value);
            temp1 = temp1.next;
        }

        while(temp2 != null) {
            if(sites.contains(temp2.value))
                System.out.print(temp2.value);
            temp2 = temp2.next;
        }
    }
}

要注意有序是指的值有序，所以有序表中存放的是節點的值，而不是節點本身，因爲值等是不代表同一個節點的。

第二種解決方式，由於是有序表，我們可以順序對比，數值較大的節點所在的鏈表等待另一條鏈表，直到另一條鏈表中出現何其相等的或者大於的，才繼續遍歷到下一節點，一次反覆反復，直到其中一個遍歷越界。

public static void printCommonPart2(Node head1, Node head2){

    Node temp1 = head1;
    Node temp2 = head2;

    while(temp1 != null && temp2 != null) {
        if(temp1.value == temp2.value){
            System.out.print(temp1.value);
        }
        else if(temp1.value > temp2.value){
            temp2 = temp2.next;
        }
        else{
            temp1 = temp1.next;
        }
    }
}

對於筆試，一切爲了時間複雜度，從思考時間和編碼速度上來說，使用雜湊表或者有序表是非常方便的，也就是用空間換了時間；

對於面試，時間複雜度仍然是第一位的，但是一定也要找到空間複雜度最優的，不去使用集合API解決問題。

3.判斷一個單鏈表是否爲迴文結構

限制條件：要求時間複雜度O(N)，空間複雜度爲O(1)；

分析：

如果不考慮空間複雜度，我們最容易的做法就是使用棧來做迴文的題目。本題就可以把鏈表全部壓入棧，然後再次遍歷鏈表，同時彈出棧，一一匹配對比，若都能對上，則就是迴文。

public static boolean isPalindrome1(Node head){

    if(head == null)
        return false;

    Stack<Integer> st = new Stack<>();
    Node temp = head;

    while(temp != null) {
       st.push(temp.value);
       temp = temp.next;
    }
    
    temp = head;

    while(temp != null) {
        if (temp.value != st.pop())
            return false;
        temp = temp.next;
    }
    
    return true;
    
}

比上面方法省一半空間的做法，就是把後半部分鏈表壓入棧中，再從頭遍歷鏈表，如果全部一一匹配上，那麼也可以判斷是迴文。

public static boolean isPalindrome2(Node head){

    if(head == null)
        return false;

    Stack<Integer> st = new Stack<>();
    Node temp= getMidNode(head).next;

    while(midNode != null) {
       st.push(midNode .value);
       midNode = midNode .next;
    }

    temp = head;

    while(!st.empty()) {
        if (temp.value != st.pop())
            return false;
        temp = temp.next;
    }
    
    return true;
    
}

public static Node getMidNode(Node head) {

    if (head.next == null || head.next.next == null)
        return head;

    //快慢指針
    Node s = head;
    Node f = head.next.next;
    
    while(f != null) {
        s = s.next;
        f = f.next == null ? null : f.next.next;
    }
    
    return s;
}

以上兩種方式都開闢了額外的記憶體空間，不符合限制條件中的空間複雜度O(1)，想要實現這一點，就得在原鏈表上去操作。上面我們做過單鏈表反轉的題目，那麼既然是判斷是否是迴文結構，迴文的特點就是正反讀一樣，那麼很自然想到把鏈表進行反轉，全部反轉的話，那就是重新構造了一個一模一樣的鏈表，還是要申請新的空間，只有在原鏈表上，反轉後半部分，這樣才能纔能實現不申請額外的記憶體空間。注意判斷結束返回之前要把改變的鏈表恢復到原樣，題目要求只是判斷是否是迴文結構。
比如：1->2->3->3->2->1
1->2->3<-3<-2<-1，其中左3節點的next指針指向null；

public static boolean isPalindrome3(Node head){

    if(head == null)
        return false;

    //反轉之後，從兩端L、R開始向中間遍歷進行匹配,Rtemp作用是最後恢復鏈表
    Node L = head;
    Node temp= getMidNode(head);
    Node R = reverseList(temp);
    Node Rtemp = R;

    

    while(L != null) {
        if (L.value != R.value){
            reverseList(Rtemp); //恢復鏈表
            return false;
        }
        L = L.next;
        R = R.next;
    }
    
    reverseList(Rtemp);//恢復鏈表
    return true;
    
}

public static Node getMidNode(Node head) {

    if (head.next == null || head.next.next == null)
        return head;

    //快慢指針
    Node s = head;
    Node f = head.next.next;
    
    while(f != null) {
        s = s.next;
        f = f.next == null ? null : f.next.next;
    }
    
    return s;
}

public static Node reverseList(Node head) {
    //指針變數，pre表示操作節點的前一個節點，初始都未null，next爲操作節點的後一個節點
    Node pre = null;
    Node next;

    while(head != null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }

    return pre;
}

這裏獲得中間節點，當鏈表有奇數個節點，返回中間節點，如果是奇數個節點，返回的是上中節點。如果有題目要求是下中節點，只需要把s指針初始指向head.next就可以了。

4.將單鏈表按某個值劃分左中右區

題目：

給定某個值和一個亂序單鏈表（整數型value），將鏈表整體的的前部分小於該值（如果有的話），中間部分等於該值（如果有的話），後部分大於該值（如果有的話）。

分析：

這個題目在鏈表中出現會感覺奇奇怪怪，很熟悉，因爲陣列的題目中算是高頻題目了，註明的荷蘭國旗問題就是這類題目的原型，排序演算法中的快排就是著名的應用之一，這裏也是可以如此解決，把鏈表的各節點放到陣列nodeArr[]裡，進行快排，再把返回的陣列重新構造出鏈表就成了。這兒就不coding了，應該很簡單的。
方法二呢就是不使用額外空間的做法，畢竟一個nodeArr[]是O(N)級別的空間複雜度。我們可以通過指針操作，先把三部分用三個鏈表表示，然後再讓三個鏈表依次連線，即可達到目的。文字描述比較不好表述，結合下圖。首先我們需要6變數。SH、ST、EH、ET、BH、BE，都是Node型別的，分別表示小於部分的頭結點，小於部分的尾節點，等於部分的頭節點，等於部分的尾節點，大於部分的頭節點和大於部分的尾節點。

public static Node classificationByNum(Node head, int num){

    //6個變數
    Node SH = null;
    Node ST= null;
    Node EH= null;
    Node ET= null;
    Node BH= null;
    Node BT= null;
    
    //遍歷鏈表，按值分成三個鏈表
    while(head!= null){
        if(head.value < num) {
            process(SH, ST, head);
        }else if(cur.value == num){
            process(EH, ET, head);
        }else {
            process(BH, BT, head);
        }
        head = head.next;
    }
    
    //將三部分連成一個鏈表返回
    if(SH != null){
        head = SH;
        ST.next = (EH != null) ? EH : BH;
        ET.next = BH;
    }else if (EH != null){
         head = EH;
         ET.next = BH;
    }else{
        head = BH;    
    }

     return head;

}

public static void process(Node nodeH, Node nodeT, Node cur) {
    if(nodeH == null && nodeT == null){
        nodeH = cur;
        nodeT = cur;
    }else{
        nodeT.next = cur;
        nodeT = cur;
    }
}

5.複製含有隨機指針的鏈表

題目：

鏈表的節點有兩個指針，一個是next，指向下一個節點，還有一個random指針，隨機指向鏈表中任意一個節點（包括null）。要求複製一個這樣的鏈表。

最簡單的方法，前面提到過，雜湊表來解決，雜湊表的key存放鏈表本身，value爲該節點的複製。遍歷兩次鏈表，第一次存放和建立節點，第二次遍歷的同時去雜湊表中查詢next和random節點對應的value值，把新建立的節點也都連線在一起。

public static Node copyRandomList1(Node head){
    
    class Node{
        public int value;
        public Node next;
        public Node random;
        
        public Node(int value) {
            this.value = value;
        }
    }

    HashMap map<Node> = new HashMap<>();
    Node temp = head;
    
    while(temp != null){
        map.put(temp, new Node(temp.value));
        temp = temp.next;
    }
    
    temp = head;
    
    while(temp != null){
        map.get(temp).next = temp.next;
        map.get(temp).random = map.get(temp.random);
    }
    
    return map.get(head);
}

筆試當然可以用上述方法，但是對於和麪試官聊就需要更好的方式了，不用雜湊表，在原鏈表上進行操作。首先複製每一個節點，並且連線在原鏈表的每個對應節點的後面，如圖所示。然後把遍歷鏈表，每次取一對，將新建立的節點的random指針進行賦值。最後分離兩個鏈表，即可完成。

如上圖所示，成對取出a A，通過a找到a的random指向c，然後把A的random賦值爲c的random。

public static Node copyRandomList2(Node head){
    
    class Node{
        public int value;
        public Node next;
        public Node random;
        
        public Node(int value) {
            this.value = value;
        }
    }

    Node temp = head;
    Node nextTemp = null;
    
    //在每個節點後複製新節點
    while(temp != null){
        nextTemp = temp.next;
        temp.next = new Node(temp.value);
        temp.next.next = nextTemp;
        temp = nextTemp;
    }
    
    temp = head;
    
    //爲新節點的random賦值
    while(temp != null){
        temp.next.random = temp.random;
        temp = temp.next.next;
    }

    temp = head;
    Node tempCopy = null;
    Node res;
    //分離鏈表
    while(temp != null) {
        nextTemp = temp.next.next;
        if(tempCopy == null)
            res = temp.next;
        tempCopy = temp.next;
        temp.next = nextTemp;
        tempCopy.next = nextTemp!=null?nextTemp.next:null;
        temp = temp.next;
    }
    
    return res;
}

6.兩單鏈表相交的一系列問題

6.1判斷鏈表是否有環

有環的鏈表的特點就是不存在指向null的節點指針，所以遍歷鏈表出現越界則必無環。那麼有環就會一直遍歷下去，前面提過有序表，就是在一個集閤中檢查是否有某個元素。那麼判斷有環也可以用相同的思路，我們遍歷表，依次把每個節點存到hashset中，如果遍歷到null則無環，如果插入過程中發現該節點在hashset中存在，則有環且入環點就爲此節點。
```
public static Node isCycleList1(Node head){
    
    HashSet<Node> set = new HashSet<>();
    Node temp = head;
    
    while(temp != null){
        if(set.contains(temp))
            return temp;
        set.add(temp);
        temp = temp.next;         
    }
   
    return null;
}
```

不用額外空間的做法呢，就是使用快慢指針，之前判斷是否爲迴文的時候也使用的這兩種方法。快慢指針的原理就是，如果鏈表有環，則快慢指針必會相遇，就像是操場跑的快的同學和跑的慢的同學，一直跑下去總會相遇（套圈）。

public static Node isCycleList2(Node head){
    
    Node s = head.next;
    Node f = s != null ? s.next : null;
    
    while(f != null){
        //第一次相遇，就中止遍歷
        if(s == f)
            break;
        s = s.next;
        f = f.next != null ? f.next.next : null;
        if(f == null)
            return null;
         
    }
    //到此處還沒有返回，則有換，且s == f，s原地不動，f回到head
    f = head;
    //每次都走一步，再次相遇就是入環點
    while(s != f){
        s = s.next;
        f = f.next;
    }
   
    return s;
}

6.2兩單鏈表（可有環）相交節點

對於兩個不知道是否有環的單鏈表是否相交，我們要做的第一步就是判斷兩個鏈表有沒有環。然後再去討論是否相交的問題，6.1的方法可以拿來直接用。

假設兩個鏈表爲L1和L2

L1和L2都無環，那麼判斷相交就是看兩個鏈表的尾節點是否爲同一個，如果相交則必有相同的尾節點。那麼找到相交節點的方法也容易，讓長鏈表先走差值步，然後再一同向前遍歷，相同的第一個節點就爲相交點。
L1和L2其中一個有環，那麼這種情況是不可能相交的，假如L1有環，L2和L1相交，那麼L2是不可能無環的。

L1和L2都有環，那麼能分爲三種情況。
3-1：兩個獨立各自有環的鏈表；
3-2：同一個入環點，這樣的情況說明兩鏈表相交在環外，把環拿掉，可以看出來可以轉換爲兩個無環鏈表相交來處理。
3-3：L1和L2入環點不同，那麼只需要任意找一條鏈表進行遍歷就可以了，假如遍歷L1，L1的入環點爲Loop1，如果遍歷過程第二次到達入環點Loop1還沒有遇到L2的入環點Loop2，則就是3-1的情況，返回null；若遇到了，就爲3-3的情況，此時相交節點返回Loop1或者Loop2都可。

public static Node isIntersect(Node L1, Node L2){
    
    if(L1 == null || L2 == null)
        return null;
    
    Node loop1 = isCycleList2(L1);
    Node loop2 = isCycleList2(L2);
    
    //倆無環單鏈表
    if(loop1 == null && loop2 == null){
        return noLoopListIntersect(L1, L2);
    }

    if(loop1 != null && loop2 != null){
        //先判斷是三種情況的哪一種
        if(loop1 == loop2){
            loop1.next = null;
            return noLoopListIntersect(L1, L2);
        }else{
        
            Node temp1 = loop1.next;
            //如果回到loop1之前遇到了loop2，返回任一入環點；如果沒有遇到程式到最後返回null
            while(temp == loop1){
                if(temp == loop2){
                    return loop1;
                }
                temp = temp.next;
            }
        }
    }
    
    return null;
}

public static Node noLoopListIntersect(Node L1, Node L2){
        Node temp = L1;
        Node temp1= null;
        int len1 = 0;
        int len2 = 0;
        Node end1;
        Node end2;
        while(temp != null) {
            if (temp.next == null)
                end1 = temp;
            temp = temp.next;
            len1++;
        }
        temp = L2;
        while(temp != null) {
            if(temp.next == null)
                end2 = temp;
            temp = temp.next;
            len2++;
        }
        if(end1 != end2)
            return null;
        int lenAbs = Math.abs(len1-len2);
        if(len1 > len2){
            temp = L1;
            temp1 = L2;
        }else{
            temp = L2;
            temp2 = L1;
        }
        
        while(lenAbs != 0){
            temp = temp.next;
            lenAbs--;
        }

        while(temp != temp2){
            temp = temp.next;
            temp2 = temp2.next;
        }
        
        return temp;
}

【鏈表】常見鏈表面試的題目及總結

0.概述

0.1鏈表的數據結構

1.鏈表反轉

1.1 單鏈表反轉

1.2 雙向鏈表反轉

2.列印兩個有序鏈表的公共部分

3.判斷一個單鏈表是否爲迴文結構

4.將單鏈表按某個值劃分左中右區

5.複製含有隨機指針的鏈表

6.兩單鏈表相交的一系列問題

6.1判斷鏈表是否有環

6.2兩單鏈表（可有環）相交節點