摘要：拿了小米和美團(tuán)的，要被延期，失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。注意，有環(huán)的鏈表，此種方法失效。已知兩個(gè)單鏈表和各自有序，把它們合并成一個(gè)鏈表依然有序

導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的offer，要被延期，offer失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。

鏈表是最?？疾斓臄?shù)據(jù)結(jié)構(gòu)

// 鏈表定義
public class Node{
    int val;//數(shù)據(jù)域
    Node next;// 指針域
    
    public Node(int val){
        this.val = val;
    }
}

基礎(chǔ)題

求單鏈表的長(zhǎng)度
考察鏈表遍歷的方法，時(shí)間復(fù)雜度為o(n)

//求單鏈表長(zhǎng)度，起手判斷鏈表是否為空，非常必要
public static int getListLength(Node head){
    //如果鏈表為空，長(zhǎng)度為0
    if(null == head){
        return 0;
    }
    // 開(kāi)始著手辦正事了
    int len = 0;
    Node cur = head;
    //如果循環(huán)判斷條件不確定，可以先寫邏輯，回頭再定條件
    while(null != cur.next){
        len++;
        cur = cur.next;
    }
    return len;
}

結(jié)點(diǎn)相對(duì)位置關(guān)系，結(jié)點(diǎn)與鏈表的相對(duì)位置關(guān)系

翻轉(zhuǎn)鏈表
鏈表中經(jīng)典解法1，引入兩個(gè)指針，然后確定其相對(duì)位置關(guān)系

迭代法
解題思路：前后兩個(gè)指針，遍歷鏈表，每遍歷一個(gè)結(jié)點(diǎn)，前面的指針將指向后面的指針，時(shí)間復(fù)雜度o(n)

public static Node getReverseList(Node head){
    if(null == head || null == head.next){
        return null;
    }
    
    Node cur = head;
    Node newHead = null;
    
    while(null != cur){
        Node preCur = cur;
        cur = cur.next;
        preCur.next = newHead;
        newHead = preCur;
    }
    
    return newHead;
}

返回單鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)
兩個(gè)指針，前面的指針超前后面指針k個(gè)位置

public static Node findLastKthNode(Node head,int k){
    if(k == 0 || null == head){
        return null;
    }
    
    Node p = head;
    Node q = head;
    
    while(k > 0 || p != null){
        p = p.next;
        k--;
    }
    
    if(k > 0 || p == null){
        return null;
    }
    
    while(p != null){
        q = q.next;
        p = p.next;
    }
    
    return q;
}

查找中間結(jié)點(diǎn)
分析：兩個(gè)指針可以解決，位置相對(duì)關(guān)系是：p指針向前移動(dòng)一步，q指針向前移動(dòng)兩步

public static Node getMiddleNode(Node head){
    if(null == head || head.next == null){
        return head;
    }
    
    Node p = head;
    Node q = head;
    
    while(p != null){
        p = p.next;
        q = q.next;
        if(p != null){
            p = p.next;
        }
    }
    
    return q;
}

從尾到頭打印單鏈表

public static void printList(Node head){
    Stack s = new Stack<>();
    
    Node cur = head;
    while(cur != null){
        s.push(cur);
        cur = cur.next;
    }
    
    while(!s.empty()){
        cur = s.pop();
        System.out.print(p.val + " ");
    }
    
    System.out.println();
}

有環(huán)問(wèn)題

判斷一個(gè)單鏈表是否有環(huán)
思路：快慢兩個(gè)指針，如果相遇，則有環(huán)

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

- **取出有環(huán)鏈表中，環(huán)的長(zhǎng)度**

思路：找到相遇的結(jié)點(diǎn)a后，讓b結(jié)點(diǎn)從a位置向下遍歷，回來(lái)后得到的結(jié)點(diǎn)數(shù)，即為環(huán)長(zhǎng)度

//方法：有環(huán)鏈表中，獲取環(huán)的長(zhǎng)度。參數(shù)node代表的是相遇的那個(gè)結(jié)點(diǎn)  
public int getCycleLength(Node node) { 
    if(node == null){
        return 0;
    }
    
    int length = 0;
    Node cur = node;
    while(cur != null){
        cur = cur.next;
        length++;
        if(cur != node){
            return length;
        }
    }
    
    return length;
}

判斷兩個(gè)鏈表相交
思路：如果兩鏈接的尾結(jié)點(diǎn)相同，則有環(huán)。注意，有環(huán)的鏈表，此種方法失效。

public static boolean isIntersect(Node head1, Node head2) {
    Node tail1 = head1;
    Node tail2 = head2;
    
    while(tail1 != null){
        tail1 = tail1.next;
    }
    
    while(tail2 != null){
        tail2 = tail2.next;
    }
    
    if(tail1 == tail2){
        return true;
    }
    
    return false;
}  

單鏈表中，取出環(huán)的起始點(diǎn)

public Node getCycleStart(Node head, int cycleLength) { 
    Node first = head;
    Node second = head;
    
    for(int i = 0; i < cycleLength; i++){
        second = second.next;
    }
    
    while(first != null && second != null){
        if(first == second){
            return first;
        }
        first = first.next;
        second = second.next;
    }
    
    return null;
}

求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)
思路：分別求出a鏈表、b鏈表的長(zhǎng)度len1、len2，如果a鏈表比b鏈表長(zhǎng)，則a提前移動(dòng)len1-len2距離，然后a、b一起向前移動(dòng)，直到引用相同。

public static Node getFirstCommonNode(Node head1, Node head2) {


    Node tail1 = head1;
    Node tail2 = head2;
    
    int len1 = 1;
    while(tail1 != null){
        tail1 = tail1.next;
        len1++;
    }
    
    int len2 = 1;
    while(tail2 != null){
        tail2 = tail2.next;
        len2++;
    }
    
    if(tail1 != tail2){
        return null;
    }
    
    Node n1 = head1;
    Node n2 = head2;
    
    if(len1 > len2){
        int k = len1 - len2;
        
        while(k != 0){
            n1 = n1.next;
            k--;
        }
    }
    
    if(len1 < len2){
        int k = len1 - len2;
        
        while(k != 0){
            n2 = n2.next;
            k--;
        }
    }
    
    while(n1 != n2){
        n1 = n1.next;
        n2 = n2.next;
    }
    
    return n1;
}  

已知兩個(gè)單鏈表head1和head2各自有序，把它們合并成一個(gè)鏈表依然有序

public static Node mergeSortedList(Node head1, Node head2){
    if(head1 == null){
        return head2;
    }
    
    if(head2 == null){
        return head1;
    }
    
    Node mergeHead = null;
    if(head1.val < head2.val){
        mergeHead = head1;
        head1 = head1.next;
        mergeHead.next = null;
    }else{
        mergeHead = head2;
        head2 = head2.next;
        mergeHead.next = null;
    }
    
    Node mergeCur = mergeHead;
    while(head1 != null && head2 != null){
        if(head1.val < head2.val){
            mergeCur.next = head1;
            head1 = head1.next;
            mergeCur = mergeCur.next;
            mergeCur.next = null;
        }else{
            mergeCur.next = head2;
            head2 = head2.next;
            mergeCur = mergeCur.next;
            mergeCur.next = null;
        }
    }
    
    if(head1 != null){
        mergeCur.next = head1; 
    }
    
    if(head2 != null){
        mergeCur.next = head2;
    }
    
    return mergeHead;
}