主頁 >  其他 > 面試官常考的15道鏈表題，你會多少？【建議收藏】

面試官常考的15道鏈表題，你會多少？【建議收藏】

2021-08-10 07:42:28 其他

面試官常考的15道鏈表題，你會多少？

鏈表題，在平時練起來感覺難度還行，但是在面試的程序中，在那種氛圍，面試者很容易因為緊張，導致面試表現不好，所以這里總結了一些鏈表最常見的練習題，反復練習，孰能生巧，希望能幫助到大家！！！

image-20210807162805497

題目在線OJ鏈接難度
反轉單向鏈表牛客網易
反轉部分單向鏈表牛客網易
在鏈表中洗掉倒數第K個節點牛客網易
環形鏈表的約瑟夫環問題牛客網中
判斷一個鏈表是否為回文結構牛客網易
將單鏈表按某值劃分左邊小、中間等于、右邊大于牛客網易
單鏈表的選擇排序牛客網易
單鏈表中每K個節點之間進行反轉LeetCode中
復制一個帶隨機指標的單鏈表LeetCode中
合并兩個有序的鏈表牛客網易
一種怪異節點的洗掉方式牛客網中
按照左右半區的方式重新組合鏈表牛客網中
在單鏈表中洗掉重復的節點LeetCode中
判斷單鏈表是否有環，若有，回傳第一個入環節點LeetCode易
//單鏈表結點
public class ListNode {
    public int val;
    public ListNode next;
    
    public ListNode(int val) {
        this.val = val;
    }
}

本期文章所有原始碼-GitHub

文章目錄

  • 面試官常考的15道鏈表題，你會多少？
    • 一、反轉單向鏈表
    • 二、反轉部分單向鏈表
    • 三、在鏈表中洗掉倒數第K個節點
    • 四、環形鏈表的約瑟夫環問題
    • 五、判斷一個鏈表是否為回文結構
    • 六、將單鏈表按某值劃分左邊小、中間等于、右邊大
    • 七、單鏈表的選擇排序
    • 八、單鏈表中每K個節點之間進行反轉
    • 九、復制一個帶隨機指標的單鏈表
    • 十、合并兩個有序的鏈表
    • 十一、一種怪異節點的洗掉方式
    • 十二、按照左右半區的方式重新組合鏈表
    • 十三、在單鏈表中洗掉重復的節點
    • 十四、判斷單鏈表是否有環，若有，回傳第一個入環節點
    • 十五、終極大招之兩個單鏈表相交的一系列問題

一、反轉單向鏈表

在線OJ鏈接

image-20210807163758128

題意：輸入一個鏈表，反轉鏈表之后，回傳新鏈表的表頭！

這道題，解法有好幾種，我們這里就討論兩種思路，

方法一： 頭插法與三指標法

反轉鏈表

頭插法：定義pre 、cur和next參考，pre 指向前驅結點，cur指向當前結點，next指向后繼結點，

  1. 首先保存后繼結點next，
  2. 當next保存之后，cur的下一個結點就指向pre，
  3. 然后pre和cur分別往下走一步，
  4. 回圈往復，由圖可知，當cur == null時，回圈結束，
//頭插法
public ListNode reverseLinkList(ListNode head) {
    if (head == null || head.next == null) { //沒有結點，或者只有一個結點的情況
        return head;
    }
    
    ListNode pre = null; //前驅結點
    ListNode cur = head; //當前結點
    ListNode next = null; //后繼結點
    while (cur != null) {
        next = cur.next; //首先保存后驅結點
        cur.next = pre; //改變鏈表的指向
        
        pre = cur; //pre和cur往下走一步
        cur = next;
    }
    return pre;
}

//三指標法---只是在頭插法的基礎之上改了一下，本質上沒有什么區別
public ListNode reverseLinkList(ListNode head) {
    if (head == null || head.next == null) { //沒有結點，或者只有一個結點的情況
        return head;
    }
    
    ListNode pre = null; //前驅結點
    ListNode cur = head; //當前結點
    ListNode next = null; //后驅結點
    ListNode newHead = null;
    while (cur != null) {
        next = cur.next; //首先保存后驅結點
        if (newHead == null) { 
            newHead = cur;
        }
        cur.next = pre; //改變鏈表的指向
        
        pre = cur; //pre和cur往下走一步
        cur = next;
    }
    return pre;
}

方法二：遞回

思想：我們只需要一直往下遞回，如果cur == null，說明pre這就是原來鏈表的最后一個結點，我們作為回傳值，直接回傳即可，遞回函式有兩個引數ListNode cur, ListNode pre，代表當前結點和上一結點，在找到最后一個結點后，回傳的程序中，將cur的下一結點連上pre就行，

public ListNode reverseLinkList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    return process(head, null); //第一次呼叫，上一結點就是null
}

public ListNode process(ListNode cur, ListNode pre) {
    if (cur == null) {
        return pre;
    }
    ListNode newHead = process(cur.next, cur); //遞回呼叫下一結點
    cur.next = pre;  //連接pre
    return newHead; //將頭結點回傳去
}

二、反轉部分單向鏈表

在線OJ鏈接

image-20210807182412316

這個題就是在反轉鏈表的基礎之上進行了改進，換湯不換藥，核心代碼還是那幾行，這道題就是需要一些細節問題，我們先看看反轉后的情況：

反轉 第2個結點到第4個結點的情況：

image-20210807184726601

由上圖可知，我們大概知道思路，該怎么對這個鏈表著手，

  1. 首先遍歷鏈表，找到需要反轉鏈表的頭結點的上一個結點，對應上圖就是1號結點，定義變數名為left
  2. 然后繼續往下遍歷鏈表，找到需要反轉鏈表的尾結點 的下一個結點，對應上圖就是5號結點，定義變數名為right
  3. 此時宣告一個函式reverse，將引數(left，開始結點，結束結點，right)，轉入進去，進行反轉，反轉后連接left和right即可
public ListNode reversePartList(ListNode head, int L, int R) {
    if (head == null || head.next == null || L > R) { //沒有結點，或者只有一個結點的情況
        return head;
    }
    
    ListNode cur = head;
    ListNode pre = null; //臨時變數 ， pre 是 cur的前驅結點
    
    ListNode left = null; //表頭的上一個結點
    ListNode right = null; //尾結點的下一個結點
    
    ListNode start = null; //需要反轉鏈表的表頭
    ListNode end = null; //需要反轉鏈表的尾結點
    for (int i = 1; i <= R && cur != null; i++) {
        if (i == L) {
            left = pre; //pre 是 cur的前驅結點
            start = cur;
        }
        if (i == R) {
            end = cur;
            right = cur.next; //反轉鏈表的尾結點  的下一結點
            break;
        } 
        pre = cur;
        cur = cur.next;
    }
    
    reverse(left, start, end, right);
    return left == null? end : head; //有可能反轉后，頭結點被換了，
}

public void reverse(ListNode left, ListNode start, ListNode end, ListNode right) {
    ListNode next = null;
    ListNode pre = right; //頭結點需要連接right，比如上圖  2號結點連接5號結點
    while (start != right) {
        next = start.next;
        start.next = pre;
        pre = start;
        start = next;
    }
    //回圈結束后，此時pre指向反轉鏈表的尾結點，也就是上圖的 4號結點
    if (left != null) {
        left.next = pre; //上圖的  1號結點連接4號結點
    }
}

請添加圖片描述

總結：這道題找出4個關鍵結點，呼叫reverse函式即可，reverse函式跟第一題的差不多，

三、在鏈表中洗掉倒數第K個節點

在線OJ鏈接

image-20210807211010819

題意：洗掉倒數第K個結點，跟另一道題很像“回傳倒數第K個結點”，都是一樣的意思，

image-20210807213027195

分析：對比上面兩幅圖，上面那一幅圖是倒著走的情況，下面這一副是正著走的情況， 我們會發現下面那一幅圖，當fast剛好走4個結點后，接下來pre和fast同時往下走一步，此時pre就是指向了2號結點，

? 也就是說，我們會發現一個規律，假設倒著走K步，我們定義兩個參考變數fast和slow，fast先正著走K步后，slow才從頭結點開始出發，此時fast和slow一起走，一次走一步，當fast來到尾結點時，此時的slow指向的結點，就是倒數第K個結點，（畫草稿圖，更容易理解）

public ListNode delBackKNode(ListNode head, int k) {
    if (head == null || k < 1) {
        return head;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    ListNode pre = null; //slow的前驅結點
    for (; fast != null; fast = fast.next) {
        if (--k < 0) {
            pre = slow; //pre緊跟著slow
            slow = slow.next;
        }
    }
    pre.next = slow.next; //C++的朋友，需要自己手動回收ListNode結點的記憶體
    return head;
}

請添加圖片描述

四、環形鏈表的約瑟夫環問題

在線OJ鏈接

image-20210807222022988

題意：總之就是一句話：給你兩個數，一個數是回圈鏈表的長度，另一個數是m，每個人報數，報到m的就出局，剩下的接著報數，回傳最后剩下的那個結點，

請添加圖片描述

分析： 從頭開始遍歷，用一個變數記錄當前報的數，pre指向前驅結點，cur指向當前結點，回圈終止條件就是還剩下一個結點的時候，

public ListNode josephusKill(ListNode head, int k) {
    if (head == null || head.next == head) { //沒有結點，或者只有一個結點的情況
        return head;
    }
    
    int count = 1; //計數
    ListNode pre = null;
    ListNode cur = head;
    while (cur != cur.next) { //當自己的next指向自己時，說明只有一個結點了
        if (count++ == k) {
            pre.next = cur.next;
            count = 1; //重置為1
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return cur;
}

這個約瑟夫環問題，還有一個進階版的，進階版的和原題一樣，只是測驗的資料要多很多，所以一個個去建立回圈鏈表，再去一個個的洗掉結點，時間效率就很低，感興趣的朋友可以去看看《程式員代碼面試指南》，書中有講解，如何通過一些規律，來推匯出剩下的那個結點，這里我們就不多講了，

回圈鏈表的約瑟夫環問題（進階）

五、判斷一個鏈表是否為回文結構

在線OJ鏈接

image-20210808091910823

題意：判斷一個單鏈表是不是回文結構， 回文結構就是：從中間為軸，左右兩邊對折起來，左右兩邊每個位置所對應的數值是一樣的，比如1221，12321就是一個回文數.

方法一：： 判斷是不是回文數，我們可以用一個容器先把整個鏈表的資料裝在一起，這里就用堆疊，比如鏈表就是1 -> 2 -> 2 -> 1 ->null;我們壓堆疊后的情況就是這樣：

請添加圖片描述

此時我們就已經將整個鏈表的全部資料壓入到堆疊中，我們都知道，堆疊是先進后出的，所以在彈出資料的時候，是先彈出堆疊頂的元素，彈出的元素，我們再去和鏈表進行比較，如果其中有不相等的，說明這個鏈表就不是回文結構，

請添加圖片描述

public boolean isPlalindromeList(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    Stack<Integer> stack = new Stack<>(); //堆疊
    ListNode cur = head;
    while (cur != null) {
        stack.push(cur.val); //壓堆疊
        cur = cur.next;
    }
    
    cur = head;
    while (cur != null) {
        if (cur.val != stack.pop()) {
            return false; //彈出的元素不相等的情況
        }
        cur = cur.next;
    }
    return true;
}

上面的代碼，就是運用堆疊來求解，當然這個方法還可以優化空間復雜度，假設我只壓入后半部分的資料，再去和前半部分鏈表進行比較，也是一樣的效果，這里就不多贅述了，自己動手實作一下吧，

方法二： 反轉后半部分的鏈表，優化空間復雜度O(1)

image-20210808101710957

分析：一個向左遍歷，一個向右遍歷，每次都比較一下，如果有一個不相等，那就不是回文結構，回傳結果前，要先把鏈表反轉回來，

 //進階解法，將右邊部分，反轉鏈表，指向中間結點
public boolean isPlalindromeList3(ListNode head, int size) { //size，是鏈表的總長度
    if (head == null || head.next == null) {
        return true;
    }

    boolean res = true;
    ListNode leftStart = head;
    ListNode rightStart = null;
    ListNode cur = head;
    for (int i = 0; i < size / 2; i++) {
        cur = cur.next;
    }

    rightStart =  reverseList(cur); //右半部分的頭結點
    cur = rightStart;
    for (int i = 0; i < size / 2; i++) {
        if (cur.val != leftStart.val) {
            res = false;
            break;
        }
        cur = cur.next;
        leftStart = leftStart.next;
    }
    reverseList(rightStart); //恢復鏈表，不需要接識訓傳值，本身上一個結點的next域，沒被修改
    return res;
}

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

六、將單鏈表按某值劃分左邊小、中間等于、右邊大

在線OJ鏈接

image-20210808103115277

題意：給你一個單鏈表，和一個數值，根據這個數值將單鏈表分為小于區、等于區和大于區，

方法一：跟“荷蘭國旗問題”一樣，我們只需將所有結點放到一個陣列里面，然后在陣列上做partition操作，具體的思想，前面的文章八大排序演算法 中的快速排序，就是參考了這個思想，可以看一看，

public ListNode listPartiton(ListNode head, int pivot) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode cur = head;
    int count = 0; //計算鏈表的長度
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    
    ListNode[] arr = new ListNode[count];
    for (int i = 0; i < count; i++) { //將所有結點放入陣列
        arr[i] = head;
        head = head.next;
    }
    
    int left = -1; //小于區域的范圍
    int right = count; //大于區域的范圍
    int index = 0; //用于遍歷陣列的下標
    while (index < right) { //只要index沒有和大于區域相遇，回圈就繼續
        if (arr[index].val == pivot) {
            index++;  //等于區域，別動，index往后走即可
        } else if (arr[index].val > pivot) {
            swap(arr, index, --right); //切記，這里index還不能動，因為從后面拿前來的資料，還沒有判斷大小
        } else {
            swap(arr, index++, ++left);
        }
    }
    
    for (int i = 1; i < count; i++) { //連接每個結點
        arr[i - 1].next = arr[i];
    }
    arr[count - 1].next = null; //最后一個結點的next，賦值null
    return arr[0];
}

public void swap(ListNode[] arr, int left, int right) {
    ListNode tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}

方法二： 方法一空間復雜度O(N)，可能還不能夠得到面試官的青睞，現在再說一種空間復雜度O(1)的解法，

分析：題目是要我分為三個區域，我們就把這三個區域分別看成是3個獨立的鏈表，每個鏈表都有頭尾指標，我們只需要6個參考變數來指向這頭尾結點即可，

如圖：

image-20210808111037535

public ListNode listPartition2(ListNode head, int pivot) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode sH = null;
    ListNode sT = null; //小于區域
    
    ListNode eH = null;
    ListNode eT = null; //等于區域
    
    ListNode bH = null;
    ListNode bT = null; //大于區域
    
    while (head != null) {
        ListNode next = head.next;
        head.next = null;
        if (head.val < pivot) {
            if (sH == null) {
                sH = head;
                sT = head;
            } else {
                sT.next = head; //尾結點去連接
                sT = head;
            }
        } else if (head.val == pivot) {
            if (eH == null) {
                eH = head;
                eT = head;
            } else {
                eT.next = head; //尾結點去連接
                eT = head;
            }
        } else {
            if (bH == null) {
                bH = head;
                bT = head;
            } else {
                bT.next = head; //尾結點去連接
                bT = head;
            }
        }
        head = next; //往后走
    }
    
    //連接三個區域
    if (sH != null) {
        sT.next = eH;
        eT = eH == null? sT : eT; //判斷等于區域是否有結點
    }
    if (bH != null) {
        eT.next = bH;
    }
    return sH != null? sH : (eH != null? eH : bH);  
}

七、單鏈表的選擇排序

在線OJ鏈接

image-20210808144845783

題意：也就是說，在單鏈表上做選擇排序，（選擇排序：在一定的范圍內，選擇最大值或者最小值，把它放到最前面，回圈往復）

方法一：也可以將所有結點放入陣列，在陣列上做選擇排序，然后再連接起來，這樣的演算法能過OJ，面試官那里可能過不了，這里就不說了，

方法二：在單鏈表的基礎之上，做選擇排序操作，我們定義一個newHead，作為新的頭結點，minPre指向最小結點的前驅結點，每一次回圈進去，尋找當前鏈表中最小的結點，使其“掛”在newHead下，

請添加圖片描述

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = null;
    ListNode tail = null;
	
    while (head != null) {
        ListNode minNode = null; //最小結點
        ListNode minPre = null; //最小結點的前驅結點
        
        ListNode pre = null; 
        ListNode cur = head;
        while (cur != null) {
            if (minNode == null || cur.val < minNode.val) {
                minPre = pre; //保存最小結點的前驅結點
                minNode = cur; //保存最小結點
            } 
            pre = cur;
            cur = cur.next;
        }
        
     	if (minNode == head) {
            head = head.next; //換頭結點的情況
        } else {
            minPre.next = minNode.next; //將最小結點拿出
        }
        
        if (newHead == null) {
            newHead = minNode;
            tail = minNode;
        } else {
            tail.next = minNode;
            tail = minNode; //尾插法
        }
    }
    tail.next = null;
    return newHead;
}

八、單鏈表中每K個節點之間進行反轉

在線OJ鏈接

image-20210808154927918

題意：根據給的K，K個一組進行反轉，也就是前面幾道題的進階版，

分析：我們可以定義參考變數start，表示需要反轉鏈表部分的開始，參考變數end表示反轉鏈表的尾結點，還有left和right，分別表示start的前驅結點和end的后驅結點，如圖：

image-20210808155919593

所以，我們只需要封裝一個reverse函式，傳遞這四個參考變數，就能實作反轉，

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k < 2) { //k=1時，等于沒有反轉
            return head;
        }
        
        ListNode left = null;
        ListNode start = head;
        ListNode cur = head;
        int count = 1;
        while (cur != null) {
            ListNode next = cur.next;
            if (count++ == k) { //反轉
                reverse(left, start, cur, cur.next); //這里的end和right，就是cur和cur.next
                if (start == head) { //更換頭結點
                    head = cur; 
                }
                left = start; //更新left和start的指向
                start = start.next; //上圖的right
                count = 1;
            }
            cur = next;
        }
        return head;
    }

    public void reverse(ListNode left, ListNode start, ListNode end, ListNode right) {
        ListNode pre = right;
        ListNode next = null;
        while (start != right) {
            next = start.next;
            start.next = pre;
            pre = start;
            start = next;
        }
        if (left != null) {
            left.next = pre; //也就是上圖的1號結點  連接4號結點
        }
    }

九、復制一個帶隨機指標的單鏈表

在線OJ鏈接

image-20210808164652174

題意：給定一個鏈表，鏈表本身除了一個next域指向下一結點以外，還有一個random域，它可以指向這個鏈表中的任意一個結點，問：怎么復制出一個一模一樣的鏈表出來，（深拷貝與淺拷貝，前期文章有講解）

方法一： 運用哈希表，復制一個一模一樣的結點出來，然后再連接起來即可，

//哈希表實作
public Node copyRandomList(Node head) {
    HashMap<Node, Node> map = new HashMap<>();
    Node cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.val)); //復制結點
        cur = cur.next;
    }

    Node res = map.get(head);
    while (head != null) {
        map.get(head).next = map.get(head.next); //復制next域
        map.get(head).random = map.get(head.random); //復制random域
        head = head.next;
    }
    return res;
}

方法二： 遍歷一遍鏈表，將每一個結點都復制一個出來，復制出來的結點連接在原來結點的后面，然后可以得到如下圖所示：

image-20210808171059796

當我們將結點復制出來，并且連接在原結點之后，我們就會清晰地看見：

假設1號結點的random -> 3號結點，那么復制的結點1號結點random = 3號結點的后驅結點，

所以這道題，整體三步：

  1. 復制結點，連接到原結點的后面
  2. 處理每個結點的random指標，（1'號結點.random = 1號結點.random.next）
  3. 然后分離兩個鏈表即可
class Node {
    public int val;
    public Node next;
    public Node random;
    public Node(int val) {
        this.val = val;
    }
}

public Node copyRandomList(Node head) {
    if (head == null) {
        return head;
    }
    //第一步-復制結點
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;
        Node node = new Node(cur.val);

        node.next = next; //連接下一結點
        cur.next = node; //新結點掛在舊結點的后面
        cur = next;
    }

    //第二步 - random指標
    cur = head;
    Node res = cur.next; //復制鏈表的頭結點
    Node copy = null;
    while (cur != null) {
        Node next = cur.next.next; //下一個舊結點
        copy = cur.next;
        copy.random = cur.random == null? null : cur.random.next; //連接random指標,需要注意null
        cur = next; 
    }

    //第三步-分離
    cur = head;
    copy = res; //指向復制鏈表的第一個結點
    while (cur != null) {
        Node next = cur.next.next; //下一個舊結點
        copy.next = next == null? null : next.next; //注意，這里需要判斷是否為null
        cur.next = next; //將原來的鏈表還原

        copy = copy.next;
        cur = next;
    }
    return res;
}

十、合并兩個有序的鏈表

在線OJ鏈接

image-20210808173625169

題意：給定了兩個已經有序的單鏈表，將它們合并在一起，且還是有序的！

分析：我們只需宣告一個參考newHead，然后兩個變數依次取出結點進行比較，誰小，誰就先掛在newHead上，回圈終止條件是其中有一個鏈表遍歷完了，回圈就結束！

  • 宣告newHead，回圈遍歷兩個鏈表
  • 取出的結點誰更小，誰就先掛newHead上
  • 回圈結束的原因是，肯定有一個鏈表遍歷完了，還剩一個鏈表直接連上newHead即可

請添加圖片描述

public ListNode mergeList(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return headA == null? headB : headA; //其中一個是null，回傳另一個鏈表
    }
    
    ListNode newHead = null;
    ListNode tail = null; //尾指標，用尾插法
    while (headA != null && headb != null) { //兩個鏈表都不是null，回圈就繼續
        if (headA.val < headB.val) {
            if (newHead == null) {
                newHead = headA;
            } else {
                tail.next = headA;
            }
             tail = headA;
            headA = headA.next; //繼續往下走
        } else {
            if (newHead == null) {
                newHead = headB;
            } else {
                tail.next = headB;
            }
             tail = headB;
            headB = headB.next; //繼續往下走
        }
    }
    
    //回圈結束后，一定是有一個鏈表遍歷完了，此時將另一個鏈表連接上即可
    tail.next = headA != null? headA : headB;
    return newHead;
}

十一、一種怪異節點的洗掉方式

在線OJ鏈接

image-20210808182329784

題意：只給你單鏈表中的一個結點（非頭結點），問：如何將給你的結點洗掉？例如： 原鏈表： 1 -> 2 -> 3 -> 4-> null ，假設給你3號結點，在沒有頭結點的情況下，如何洗掉3號結點？

可能有人會說：將給你的結點，賦值為null不就行了嗎？

答案：肯定是不行的，給你的node結點，只是一個參考（地址），而在java中，變數是在堆疊上開辟的，直接賦值為null，只是讓這個變數找不到node結點了而已，具體的，畫一畫堆疊區和堆區的記憶體圖，你或許就明白了，

分析：這道題，有一定的局限性，如果結點的資料只是普通的資料，我們可以直接將下一個結點的資料覆寫到node結點上，然后node去連接下一個結點的下一個結點，切記：如果給你的node，是尾結點的話，這道題就沒有解，如圖：

image-20210808184038251

public void delStrangerNode(ListNode node) {
    if (node == null || node.next == null) {
        return;
    }
    node.val = node.next.val;
    node.next = node.next.next;
}

注：要跟面試過說清楚情況，這樣的方式，其實并不是洗掉了結點，只是進行了資料的覆寫，假設這一個結點時一個很大的工程，又或者是一個服務器，如果去進行資料的覆寫，工程量還是很大的，

十二、按照左右半區的方式重新組合鏈表

在線OJ鏈接

image-20210808201503818

題意：先將單鏈表從中間分開，分為兩個鏈表，然后這兩個鏈表交叉著插入結點，得到新的鏈表，

整體分為兩步：

  • 使用快慢指標，得到整個鏈表的中間結點，分為兩個鏈表
  • 交叉著穿插結點，得到新的鏈表

image-20210808203228937

由上圖，我們可以發現當fast和slow停下來的時候，slow的下一結點就是當前鏈表的中間結點，此時我們就可以分為兩個鏈表了，

請添加圖片描述

public ListNode againCombinationList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    //當回圈停下的時候，slow的下一結點就是整個鏈表的中間結點
    ListNode right = slow.next; //右半部分的鏈表
    slow.next = null; //置為null
    ListNode left = head; //左半部分的鏈表
    while (left.next != null) {
        ListNode next = right.next;
        right.next = left.next;
        left.next = right;
        
        left = right.next; 
        right = next;
    }
    left.next = right;
    return head;
}

十三、在單鏈表中洗掉重復的節點

在線OJ鏈接

image-20210808212453595

分析：首先看到洗掉重復結點，我就想到了HashSet集合，做容器，遍歷一遍鏈表，將所有資料添加到集合中，最后再連接起來，但是這樣的話，空間復雜度就高了，這樣的思路只是適合在筆試的時候用，在面試的時候，入不了面試官的眼的，

? 所以我們只能想辦法在鏈表上直接動手了，一開始，我們以鏈表的第一個結點作為目標，在這個結點的后面的結點做遍歷，如果剩下的結點中沒有與目標結點相等的，我們的目標結點就轉換到下一個結點，繼續做這樣的遍歷，時間復雜度O(N2)，

public ListNode removeDuplicateNodes(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode cur = head;
    ListNode pre = null;
    ListNode next = null;
    while (cur != null) {
        next = cur.next; //首先保存cur的下一結點，在這個結點上去做比較
        pre = cur;
        while (next != null) { //從next往下走，每一個結點都與cur比較
            if (cur.val == next.val) {
                pre.next = next.next; //相等的情況，pre直接連接下一個結點
            } else {
                pre = next;
            }
            next = next.next;
        }
        cur = cur.next;
    }
    return head;
}

十四、判斷單鏈表是否有環，若有，回傳第一個入環節點

在線OJ鏈接

image-20210808215405806

分析：有一道鏈表題是判斷給定鏈表是否有環，這道題就是在有環的基礎之上，需要回傳第一個入環的結點，如果就是入環的第一個結點；

image-20210808220046040

此時的3號結點，我們就稱為入環的第一個結點，

如何找到這個入環結點并回傳？

還是要引入小學的數學問題，追趕問題，引入slow和fast指標，slow每次走一步，fast每次走兩步，如果給定的鏈表是有環的，slow和fast肯定能在環上相遇（fast的速度是slow的兩倍），此時我們讓fast從head重新出發，這次slow和fast每次只有一步，這樣slow和fast肯定能在入環結點處相遇，至于如何證明這個問題，我就不多說了，動圖如下：

請添加圖片描述

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }  
    ListNode slow = head;
    ListNode fast = head; //都從第一個結點出發
    while (fast != null && fast.next != null) { //如果不是回圈鏈表，就退出
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) { //相等了
            fast = head; //從頭開始
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    } 
    return null;
}

十五、終極大招之兩個單鏈表相交的一系列問題

題目：在本題中，單鏈表可能有環，也可能無環，給定兩個單鏈表的頭結點head1和head2，這兩個鏈表可能相交，也可能不相交，

請實作一個函式，如果兩個鏈表相交，請回傳相交的第一個結點；如果不相交，回傳null即可，

要求：如果鏈表1的長度為N，鏈表2的長度為M,時間復雜度請達到O(N+M)，額外空間復雜度請達到O(1)，

出自《程式員代碼面試指南》一書，

注：如果其中一個鏈表有環，另一個鏈表無環，那么這兩個鏈表肯定不相交，

這道題我就留個大家自己研究啦，因為暫時還沒找到OJ題，所以就不講啦，我會將原始碼放到GitHub上，

好啦，各位朋友！本期更新就到此結束啦！鏈表題說難也不是很難，說簡單也算不上，這畢竟是面試官必問的相關題，好好研究研究，趕快上手寫代碼吧！

下期見啦！！！拜拜

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292722.html

標籤：其他

上一篇：【Leetcode演算法熱題 --- 鏈表篇】鏈表中倒數第k個節點

下一篇：2021年8月前端面試題最新出爐(二)—HTTP協議

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂