鏈表面試題常用數(shù)據(jù)結構和技巧

1）使用容器(哈希表、數(shù)組等)

2）快慢指針

快慢指針

1）輸入鏈表頭節(jié)點，奇數(shù)長度返回中點，偶數(shù)長度返回上中點

2）輸入鏈表頭節(jié)點，奇數(shù)長度返回中點，偶數(shù)長度返回下中點

3）輸入鏈表頭節(jié)點，奇數(shù)長度返回中點前一個，偶數(shù)長度返回上中點前一個

4）輸入鏈表頭節(jié)點，奇數(shù)長度返回中點前一個，偶數(shù)長度返回下中點前一個

代碼如下

/**
 * 整體流程都是快指針一次走兩步，慢指針一次走一步，當快指針走到鏈表尾部是，
 * 慢指針正好走到整個鏈表中部位置（位置需要根據(jù)要求作出些許調整）
 */
public class FastLowPoint01 {
    //輸入鏈表頭節(jié)點，奇數(shù)長度返回中點，偶數(shù)長度返回上中點
    public static Node getMidNode1(Node head){
        if(head == null || head.next == null || head.next.next == null){
            // 為空時返回空，一個節(jié)點奇數(shù)返回一個，兩個節(jié)點偶數(shù)返回上中點
            return head;
        }
        // 至少有兩個指針
        // o -> o -> o -> o -> o --null
        Node low = head;
        Node fast = head.next;
        while (fast != null && fast.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
    // 輸入鏈表頭節(jié)點，奇數(shù)長度返回中點，偶數(shù)長度返回下中點
    public static Node getMidNode2(Node head){
        if(head == null || head.next == null){
            return head;
        }
        // o -> o -> o -> o -> o --null
        Node low = head;
        Node fast = head;
        while (fast != null && fast.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
    // 輸入鏈表頭節(jié)點，奇數(shù)長度返回中點前一個，偶數(shù)長度返回上中點前一個
    public static Node getMidNode3(Node head){
        if (head == null || head.next == null || head.next.next == null){
            return null;
        }

        // o -> o -> o -> o -> o --null
        Node low = head;
        Node fast = head.next.next;
        while (fast != null && fast.next != null && fast.next.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }

    // 輸入鏈表頭節(jié)點，奇數(shù)長度返回中點前一個，偶數(shù)長度返回下中點前一個
    public static Node getMidNode4(Node head){
        if(head == null || head.next == null){
            // o
            return null;
        }
        Node low = head;
        Node fast = head.next;
        // o -> o -> o -> o -> o --null
        while (fast != null && head.next != null && fast.next.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
}

常見面試題

給定一個單鏈表的頭節(jié)點head，請判斷該鏈表是否為回文結構。

方法一，利用棧。
1）先遍歷一遍鏈表把節(jié)點加入棧中。
2）彈出一個節(jié)點，從頭遍歷鏈表，比較。

public class PalindromeLinked {
    // 棧
    public static boolean isPalindrome(Node head){
        if(head == null){
            return true;
        }

        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        cur = head;
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            if(pop.value != cur.value){
                return false;
            }
            cur = cur.next;
        }

        return true;
    }

    // 雙指針
    public static boolean isPalindrome2(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node low = head;
        Node fast = head.next;
        // o -> o -> o -> o -> o
        while (fast != null && fast.next != null){
            low = low.next;
            fast = fast.next.next;
        }
        // 此時low指向鏈表中點,從low 開始反轉鏈表

        Node pre = null;
        Node cur = low;

        while (cur != null){
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        Node tail = pre;
        cur = head;
        while (cur != null && pre != null){
            if(cur.value != pre.value){
                return false;
            }
            cur = cur.next;
            pre = pre.next;
        }
        pre = null;
        cur = tail;
        while (cur != null){
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return true;
    }
}

將單向鏈表按某值劃分成左邊小、中間相等、右邊大的形式
1）把鏈表放入數(shù)組里，在數(shù)組上做partition（筆試用）。
2）分成小、中、大三部分，再把各個部分之間串起來（面試用）。
克隆鏈表
一種特殊的單鏈表節(jié)點類描述如下
class Node {
int value;
Node next;
Node rand;
Node(int val) { value = val; }
}
rand指針是單鏈表節(jié)點結構中新增的指針，rand可能指向鏈表中的任意一個節(jié)點，也可能指向null。
給定一個由Node節(jié)點類型組成的無環(huán)單鏈表的頭節(jié)點 head，請實現(xiàn)一個函數(shù)完成這個鏈表的復制，并返回復制的新鏈表的頭節(jié)點。
【要求】
時間復雜度O(N)，額外空間復雜度O(1)

public class CopyLinked {

    public static Node copyLinked(Node oldHead){
        if(oldHead == null){
            return null;
        }

        // 在原鏈表中間增加復制節(jié)點
        Node cur = oldHead;
        while (cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }

        // 重新遍歷鏈表，把克隆節(jié)點的random連好
        cur = oldHead;
        while (cur != null){
            // 獲取原節(jié)點的random節(jié)點
            Node randomOld = cur.random;
            // 克隆節(jié)點的random節(jié)點
            cur.next.random = randomOld == null ? null : randomOld.next;
            cur = cur.next.next;
        }
        // 分離新老鏈表
        cur = oldHead;
        Node res = oldHead.next;
        while (cur != null){
            Node oldNext = cur.next.next;
            Node next = cur.next;
            cur.next = next.next;
            next.next = cur.next == null ? null : cur.next.next;
            cur = oldNext;
        }
        return res;
    }
}

給定兩個可能有環(huán)也可能無環(huán)的單鏈表，頭節(jié)點head1和head2。請實現(xiàn)一個函數(shù)，如果兩個鏈表相交，請返回相交的第一個節(jié)點。如果不相交，返回null 。
【要求】
如果兩個鏈表長度之和為N，時間復雜度請達到O(N)，額外空間復雜度請達到O(1)。

public class TwoLinked {

    public  Node getFirstNode(Node node1,Node node2){

        if(node1 == null || node2== null){
            return null;
        }
        // 如果量表都沒有環(huán)
        if(isLoop(node1) == null && isLoop(node2) == null){
            // 兩個鏈表都沒有環(huán)
            return notLoop(node1,node2);
        }else if (isLoop(node1)!=null && isLoop(node2)!=null){
            // 兩個鏈表都有環(huán)
            return bothLoop(node1,node2);
        }
        // 一個鏈表有環(huán)，一個鏈表沒有環(huán)是不存在的
        return null;
    }

    private Node notLoop(Node node1,Node node2){
        // 兩個無環(huán)鏈表，先看為指針是否相等
        int n1 = 0;
        int n2 = 0;
        Node cur1 = node1;
        Node cur2 = node2;
        while (cur1.next != null){
            n1++;
            cur1 = cur1.next;
        }

        while (cur2.next != null){
            n2++;
            cur2 = cur2.next;
        }
        if(cur1 != cur2){
            return null;
        }
        // 長鏈表
        cur1 = n1 > n2 ? node1 : node2;
        // 短鏈表
        cur2 = n1 > n2 ? node2 : node1;
        int n = Math.abs(n1-n2);
        // 長鏈表先走n步
        while (n > 0){
            cur1 = cur1.next;
            n--;
        }
        // 一起走
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    private Node bothLoop(Node node1,Node node2){
        // 求兩個節(jié)點的入環(huán)節(jié)點
        Node loop1 = isLoop(node1);
        Node loop2 = isLoop(node2);
        if(loop1 == loop2){
            // 變換成兩個無環(huán)鏈表求第一個相交節(jié)點問題
            int n1 = 0;
            int n2 = 0;
            Node cur1 = node1;
            Node cur2 = node2;
            while (cur1 != loop1){
                n1++;
                cur1 = cur1.next;
            }
            while (cur2 != loop1){
                n2++;
                cur2 = cur2.next;
            }

            cur1 = n1 > n2 ? node1:node2 ;
            cur2 = n1 > n2 ? node2:node1 ;
            int n = Math.abs(n1-n2);
            while (n > 0){
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else{
            Node cur = loop1.next;
            while (cur != loop1){
                if(cur == loop2){
                    return loop1;
                }
                cur = cur.next;
            }
            return null;
        }
    }

    // 判斷鏈表是否有環(huán),返回第一個入環(huán)節(jié)點
    private Node isLoop(Node node){
        if(node == null || node.next == null || node.next.next==null){
            // 一個節(jié)點，或者兩個節(jié)點都沒有環(huán)
            return null;
        }
        // 快慢指針
        Node fast = node.next.next;
        Node low = node.next;
        while (fast != low){
            if(fast.next == null || low.next == null){
                return null;
            }
            fast = fast.next.next;
            low = low.next;
        }
        // 此時fast 回到頭結點
        fast = node;
        while (fast != low){
            // 再次相遇則為入環(huán)節(jié)點
            if(fast == low){
                break;
            }
            fast = fast.next;
            low = low.next;
        }

        return fast;
    }   
}

能不能不給單鏈表的頭節(jié)點，只給想要刪除的節(jié)點，就能做到在鏈表上把這個點刪掉？

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結構與算法學習筆記（基礎班六）---鏈表

數(shù)據(jù)結構與算法學習筆記（基礎班六）---鏈表

鏈表面試題常用數(shù)據(jù)結構和技巧

快慢指針

常見面試題

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結構與算法學習筆記（基礎班六）---鏈表

鏈表面試題常用數(shù)據(jù)結構和技巧

快慢指針

常見面試題

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av