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

導師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的offer，要被延期，offer失效，工作重新找。把準備過程紀錄下來，共勉。

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

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

基礎(chǔ)題

求單鏈表的長度
考察鏈表遍歷的方法，時間復雜度為o(n)

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

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

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

迭代法
解題思路：前后兩個指針，遍歷鏈表，每遍歷一個結(jié)點，前面的指針將指向后面的指針，時間復雜度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個結(jié)點
兩個指針，前面的指針超前后面指針k個位置

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é)點
分析：兩個指針可以解決，位置相對關(guān)系是：p指針向前移動一步，q指針向前移動兩步

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)問題

判斷一個單鏈表是否有環(huán)
思路：快慢兩個指針，如果相遇，則有環(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)的長度**

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

//方法：有環(huán)鏈表中，獲取環(huán)的長度。參數(shù)node代表的是相遇的那個結(jié)點  
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;
}

判斷兩個鏈表相交
思路：如果兩鏈接的尾結(jié)點相同，則有環(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)的起始點

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

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

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

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

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