?申明： 未經(jīng)許可，禁止以任何形式轉(zhuǎn)載，若要引用，請(qǐng)標(biāo)注鏈接地址。 全文共計(jì)10077字，閱讀大概需要10分鐘
??更多學(xué)習(xí)內(nèi)容， 歡迎??關(guān)注??文末我的個(gè)人微信公眾號(hào)：不懂開發(fā)的程序猿
個(gè)人網(wǎng)站：https://jerry-jy.co/

LeetCode算法小抄

Collection 子接口之 Queue (LeetCode上經(jīng)常用，手撕算法題?。?！)

Queue 與 Deque 的區(qū)別

Queue 是單端隊(duì)列，只能從一端插入元素，另一端刪除元素，實(shí)現(xiàn)上一般遵循 先進(jìn)先出（FIFO） 規(guī)則。

Queue 擴(kuò)展了 Collection 的接口，根據(jù) 因?yàn)槿萘繂栴}而導(dǎo)致操作失敗后處理方式的不同 可以分為兩類方法: 一種在操作失敗后會(huì)拋出異常，另一種則會(huì)返回特殊值

Deque 是雙端隊(duì)列，在隊(duì)列的兩端均可以插入或刪除元素。

Deque 擴(kuò)展了 Queue 的接口, 增加了在隊(duì)首和隊(duì)尾進(jìn)行插入和刪除的方法，同樣根據(jù)失敗后處理方式的不同分為兩類：

事實(shí)上，Deque 還提供有 push() 和 pop() 等其他方法，可用于模擬棧。

peek函數(shù)使用

Java中的peek函數(shù)是用于取出隊(duì)列中隊(duì)頭元素，但不會(huì)將其從隊(duì)列中移除。這樣，使用peek函數(shù)可以查看隊(duì)列中的隊(duì)頭元素，而不會(huì)改變隊(duì)列的狀態(tài)。

例如：

Queue<Integer> queue = new LinkedList<>(); 

queue.add(1); 

queue.add(2); 

queue.add(3);

// 查看隊(duì)頭元素 Integer first = queue.peek(); // 返回1

// 查看隊(duì)列中的元素 System.out.println(queue); // 輸出[1, 2, 3]

peek函數(shù)在Java的Queue接口中定義，可以通過實(shí)現(xiàn)該接口的類來使用該函數(shù)。常見的實(shí)現(xiàn)類有LinkedList、PriorityQueue等。

使用peek函數(shù)時(shí)，需要注意以下幾點(diǎn)：

1. 如果隊(duì)列為空，peek函數(shù)會(huì)返回null，而不會(huì)拋出異常。因此，使用peek函數(shù)時(shí)，需要先判斷隊(duì)列是否為空，避免出現(xiàn)空指針異常。
2. peek函數(shù)返回的是隊(duì)列中的隊(duì)頭元素的副本，而不是隊(duì)列中的實(shí)際元素。因此，對(duì)返回的元素進(jìn)行修改并不會(huì)改變隊(duì)列中的實(shí)際元素。
3. 如果隊(duì)列中的元素為null，peek函數(shù)也會(huì)返回null。因此，使用peek函數(shù)時(shí)，需要注意區(qū)分隊(duì)列為空和隊(duì)列中存在null元素的情況。
4. 如果隊(duì)列中的元素為不可變對(duì)象

樹

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目

樹的度：樹中結(jié)點(diǎn)的最大的度

滿二叉樹：高度為h，并且由 2^? –1個(gè)結(jié)點(diǎn)的二叉樹，被稱為滿二叉樹，滿二叉樹的結(jié)點(diǎn)的度要么為0（葉子結(jié)點(diǎn)），要么為2（非葉子結(jié)點(diǎn)）

完全二叉樹：一棵二叉樹中，只有最下面兩層結(jié)點(diǎn)的度可以小于2，并且最下一層的葉結(jié)點(diǎn)集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹。

特點(diǎn)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

二叉查找樹：二叉查找樹，又被稱為二叉搜索樹。其特點(diǎn)如下：設(shè)x為二叉查找樹中的一個(gè)結(jié)點(diǎn)，x節(jié)點(diǎn)包含關(guān)鍵字key，一句話就是左孩子比父節(jié)點(diǎn)小，右孩子比父節(jié)點(diǎn)大，還有一個(gè)特性就是 中序遍歷可以讓結(jié)點(diǎn)有序。

二叉堆和二叉樹區(qū)別：

• 二叉堆在邏輯上其實(shí)是一種特殊的二叉樹（完全二叉樹）
• 二叉堆是存儲(chǔ)數(shù)組，一般的鏈表二叉樹，我們操作節(jié)點(diǎn)的指針，而在二叉堆里，我們把數(shù)組索引作為指針
• 二叉堆還分為最大堆和最小堆。最大堆的性質(zhì)是：每個(gè)節(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)。類似的，最小堆的性質(zhì)是：每個(gè)節(jié)點(diǎn)都小于等于它的子節(jié)點(diǎn)。

優(yōu)先級(jí)隊(duì)列(Priority Queue)

這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)很有用的功能，你插入或者刪除元素的時(shí)候，元素會(huì)自動(dòng)排序，這底層的原理就是二叉堆的操作。優(yōu)先級(jí)隊(duì)列有兩個(gè)主要 API，分別是 insert 插入一個(gè)元素和 delMax 刪除最大元素（如果底層用最小堆，那么就是 delMin）。

插入是先插到最后，然后上浮到正確位置；刪除是調(diào)換位置后再刪除，然后下沉到正確位置

放入PriorityQueue的元素，必須實(shí)現(xiàn)Comparable接口，沒有實(shí)現(xiàn)Comparable接口怎么辦？PriorityQueue允許我們提供一個(gè)Comparator對(duì)象來判斷兩個(gè)元素的順序

面試：說一說 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其與 Queue 的區(qū)別在于元素出隊(duì)順序是與優(yōu)先級(jí)相關(guān)的，即總是優(yōu)先級(jí)最高的元素先出隊(duì)。

這里列舉其相關(guān)的一些要點(diǎn)：

• PriorityQueue 利用了二叉堆的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的，底層使用可變長(zhǎng)的數(shù)組來存儲(chǔ)數(shù)據(jù)
• PriorityQueue 通過堆元素的上浮和下沉，實(shí)現(xiàn)了在 O(logn) 的時(shí)間復(fù)雜度內(nèi)插入元素和刪除堆頂元素。
• PriorityQueue 是非線程安全的，且不支持存儲(chǔ) NULL 和 non-comparable 的對(duì)象。
• PriorityQueue 默認(rèn)是小頂堆，但可以接收一個(gè) Comparator 作為構(gòu)造參數(shù)，從而來自定義元素優(yōu)先級(jí)的先后。

鏈表

1、單鏈表

遞歸反轉(zhuǎn)

經(jīng)典：206. 反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 如果鏈表為空或者只有一個(gè)節(jié)點(diǎn)的時(shí)候，反轉(zhuǎn)結(jié)果就是它自己，直接返回即可
        if(head == null || head.next == null){
            return head;
        }
        // 遞歸反轉(zhuǎn)
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

衍生題目：

反轉(zhuǎn)鏈表前 N 個(gè)節(jié)點(diǎn)

ListNode successor = null; // 后驅(qū)節(jié)點(diǎn)

// 反轉(zhuǎn)以 head 為起點(diǎn)的 n 個(gè)節(jié)點(diǎn)，返回新的頭結(jié)點(diǎn)
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 記錄第 n + 1 個(gè)節(jié)點(diǎn)
        successor = head.next;
        return head;
    }
    // 以 head.next 為起點(diǎn)，需要反轉(zhuǎn)前 n - 1 個(gè)節(jié)點(diǎn)
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 讓反轉(zhuǎn)之后的 head 節(jié)點(diǎn)和后面的節(jié)點(diǎn)連起來
    head.next = successor;
    return last;
}

92. 反轉(zhuǎn)鏈表 II

給你單鏈表的頭指針 head 和兩個(gè)整數(shù) left 和 right ，其中 left <= right 。請(qǐng)你反轉(zhuǎn)從位置 left 到位置 right 的鏈表節(jié)點(diǎn)，返回 反轉(zhuǎn)后的鏈表 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // base case
        if(left == 1){
            return reverseN(head, right);
        }
        // 前進(jìn)到反轉(zhuǎn)的起點(diǎn)觸發(fā) base case
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    // 后繼節(jié)點(diǎn)
    ListNode successor = null;
    // 反轉(zhuǎn)以 head 為起點(diǎn)的 n 個(gè)節(jié)點(diǎn)，返回新的頭結(jié)點(diǎn)
    private ListNode reverseN(ListNode head, int n){
        if(n == 1){
            // 記錄第 n + 1 個(gè)節(jié)點(diǎn)
            successor = head.next;
            return head;
        }
        // 以 head.next 為起點(diǎn)，需要反轉(zhuǎn)前 n - 1 個(gè)節(jié)點(diǎn)
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 讓反轉(zhuǎn)之后的 head 節(jié)點(diǎn)和后面的節(jié)點(diǎn)連起來
        head.next = successor;
        return last;
    }
}

迭代反轉(zhuǎn)

給定鏈表頭結(jié)點(diǎn)，如何反轉(zhuǎn)整個(gè)鏈表？

「反轉(zhuǎn)以 a 為頭結(jié)點(diǎn)的鏈表」其實(shí)就是「反轉(zhuǎn) a 到 null 之間的結(jié)點(diǎn)」

// 反轉(zhuǎn)以 a 為頭結(jié)點(diǎn)的鏈表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐個(gè)結(jié)點(diǎn)反轉(zhuǎn)
        cur.next = pre;
        // 更新指針位置
        pre = cur;
        cur = nxt;
    }
    // 返回反轉(zhuǎn)后的頭結(jié)點(diǎn)
    return pre;
}

反轉(zhuǎn) a 到 b 之間的結(jié)點(diǎn)

/** 反轉(zhuǎn)區(qū)間 [a, b) 的元素，注意是左閉右開 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 終止的條件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反轉(zhuǎn)后的頭結(jié)點(diǎn)
    return pre;
}

25. K 個(gè)一組翻轉(zhuǎn)鏈表[hard]

給你鏈表的頭節(jié)點(diǎn) head ，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回修改后的鏈表。

k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際進(jìn)行節(jié)點(diǎn)交換。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        // 區(qū)間 [a, b) 包含 k 個(gè)待反轉(zhuǎn)元素
        ListNode a, b;
        a = b = head;
        for(int i = 0; i < k; i++){
            // 不足 k 個(gè)，不需要反轉(zhuǎn)，base case
            if(b == null) return head;
            b = b.next;
        }
        // 反轉(zhuǎn)前 k 個(gè)元素
        ListNode newHead = reverse(a, b);
        // 遞歸反轉(zhuǎn)后續(xù)鏈表并連接起來
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    /** 反轉(zhuǎn)區(qū)間 [a, b) 的元素，注意是左閉右開 */
    private ListNode reverse(ListNode a, ListNode b){
        ListNode pre, cur, nxt;
        pre = null; cur = a; nxt = a;
        while(cur != b){
            // 逐個(gè)結(jié)點(diǎn)反轉(zhuǎn)
            nxt = cur.next;
            cur.next = pre;
            // 更新指針位置
            pre = cur;
            cur = nxt;
        }
        // 返回反轉(zhuǎn)后的頭結(jié)點(diǎn)
        return pre;
    }
}

2、雙鏈表

21. 合并兩個(gè)有序鏈表

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

思路：

• 先初始化一個(gè)dummy = new ListNode(0) 為空的節(jié)點(diǎn)，定義一個(gè)ListNode p = dummy用來方便指針移動(dòng)
• 如果list1 list2都不為空，作比較，小的賦值給p.next，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      // 虛擬頭結(jié)點(diǎn)
      ListNode dummy = new ListNode(0);
      ListNode p = dummy;
      ListNode p1 = list1, p2 = list2;

      while(p1 != null && p2 != null){
        // 比較 p1 和 p2 兩個(gè)指針
        // 將值較小的的節(jié)點(diǎn)接到 p 指針
          if(p1.val > p2.val){
             p.next = p2;
             p2 = p2.next;
          }else{
              p.next = p1;
              p1 = p1.next;
          }
          // p 指針不斷前進(jìn)
          p = p.next;
      }
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
    
    return dummy.next;
    }
}

86. 分隔鏈表

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x ，請(qǐng)你對(duì)鏈表進(jìn)行分隔，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
         // 存放小于 x 的鏈表的虛擬頭結(jié)點(diǎn)
        ListNode dummy1 = new ListNode(0);
        // 存放大于等于 x 的鏈表的虛擬頭結(jié)點(diǎn)
        ListNode dummy2 = new ListNode(0);
        // p 負(fù)責(zé)遍歷原鏈表，類似合并兩個(gè)有序鏈表的邏輯
        ListNode p = head;
        // p1, p2 指針負(fù)責(zé)生成結(jié)果鏈表
        ListNode p1 = dummy1, p2 = dummy2;
        // 這里是將一個(gè)鏈表分解成兩個(gè)鏈表
        while(p != null){
            if(p.val > x){
                p2.next = p;
                p2 = p2.next;
            }else{
                p1.next = p;
                p1 = p1.next;
            }
            // 斷開原鏈表中的每個(gè)節(jié)點(diǎn)的 next 指針
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        // 連接兩個(gè)鏈表
       p1.next= dummy2.next;
       return dummy1.next;
    }
}

23. 合并 K 個(gè)升序鏈表[hard]

給你一個(gè)鏈表數(shù)組，每個(gè)鏈表都已經(jīng)按升序排列。

請(qǐng)你將所有鏈表合并到一個(gè)升序鏈表中，返回合并后的鏈表。

這個(gè)算法是面試?？碱}，它的時(shí)間復(fù)雜度是多少呢？算法整體的時(shí)間復(fù)雜度是 O(Nlogk)，其中 k 是鏈表的條數(shù)，N 是這些鏈表的節(jié)點(diǎn)總數(shù)。

**思路：**合并 k 個(gè)有序鏈表的邏輯類似合并兩個(gè)有序鏈表，難點(diǎn)在于，如何快速得到 k 個(gè)節(jié)點(diǎn)中的最小節(jié)點(diǎn)，接到結(jié)果鏈表上？考慮使用優(yōu)先隊(duì)列，把k個(gè)鏈表加入隊(duì)列中，當(dāng)隊(duì)列不為空，拉出一個(gè)元素，指向到p.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }
        // 虛擬頭結(jié)點(diǎn)
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        // 優(yōu)先級(jí)隊(duì)列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val));
        // 將 k 個(gè)鏈表的頭結(jié)點(diǎn)加入最小堆
        for(ListNode head : lists){
            if(head!=null){
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){
             // 獲取最小節(jié)點(diǎn)，接到結(jié)果鏈表中
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
             // p 指針不斷前進(jìn)
            p = p.next;
        }
        return dummy.next;
    }
}

3、雙指針類型的題目

雙指針技巧主要分為兩類：左右指針和快慢指針。

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

注意細(xì)節(jié)：又使用了虛擬頭結(jié)點(diǎn)的技巧，也是為了防止出現(xiàn)空指針的情況，比如說鏈表總共有 5 個(gè)節(jié)點(diǎn)，題目就讓你刪除倒數(shù)第 5 個(gè)節(jié)點(diǎn)，也就是第一個(gè)節(jié)點(diǎn)，那按照算法邏輯，應(yīng)該首先找到倒數(shù)第 6 個(gè)節(jié)點(diǎn)。但第一個(gè)節(jié)點(diǎn)前面已經(jīng)沒有節(jié)點(diǎn)了，這就會(huì)出錯(cuò)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 先找到倒數(shù)第n+1個(gè)
        ListNode x = findFromEnd(dummy, n+1);
        x.next = x.next.next;
        return dummy.next;
    }
    // 返回鏈表的倒數(shù)第 k 個(gè)節(jié)點(diǎn)
    private ListNode findFromEnd(ListNode head, int k){
        ListNode p1 = head;
        for(int i = 0; i < k; i++){
            p1 = p1.next;
        }
        ListNode p2 = head;
        while(p1 != null){
            p2 = p2.next;
            p1 = p1.next;
        }
        return p2;
    }
}

4、快慢指針的問題

876. 鏈表的中間結(jié)點(diǎn)

給你單鏈表的頭結(jié)點(diǎn) head ，請(qǐng)你找出并返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

思路：

我們讓兩個(gè)指針 slow 和 fast 分別指向鏈表頭結(jié)點(diǎn) head。

每當(dāng)慢指針 slow 前進(jìn)一步，快指針 fast 就前進(jìn)兩步，這樣，當(dāng) fast 走到鏈表末尾時(shí)，slow 就指向了鏈表中點(diǎn)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // 快慢指針初始化指向 head
        ListNode fast = head, slow = head; 
        // 快指針走到末尾時(shí)停止
        while(fast != null && fast.next != null){
            // 慢指針走一步，快指針走兩步
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

判斷鏈表是否包含環(huán)

判斷鏈表是否包含環(huán)屬于經(jīng)典問題了，解決方案也是用快慢指針：

每當(dāng)慢指針 slow 前進(jìn)一步，快指針 fast 就前進(jìn)兩步。

如果 fast 最終遇到空指針，說明鏈表中沒有環(huán)；如果 fast 最終和 slow 相遇，那肯定是 fast 超過了 slow 一圈，說明鏈表中含有環(huán)。

boolean hasCycle(ListNode head) {
    // 快慢指針初始化指向 head
    ListNode slow = head, fast = head;
    // 快指針走到末尾時(shí)停止
    while (fast != null && fast.next != null) {
        // 慢指針走一步，快指針走兩步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指針相遇，說明含有環(huán)
        if (slow == fast) {
            return true;
        }
    }
    // 不包含環(huán)
    return false;
}

160. 相交鏈表

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null 。

思路：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // 計(jì)算兩條鏈表的長(zhǎng)度
        for(ListNode p1 = headA; p1 != null; p1 = p1.next){
            lenA++;
        }
        for(ListNode p2 = headB; p2 != null; p2 = p2.next){
            lenB++;
        }
        // 讓 p1 和 p2 到達(dá)尾部的距離相同
        ListNode p1 = headA, p2 = headB;
        if(lenA > lenB){
            for(int i = 0; i < lenA -lenB; i++){
                p1 = p1.next;
            }
        } else {
            for(int i = 0; i < lenB - lenA; i++){
                p2 = p2.next;
            }
        }
        // 看兩個(gè)指針是否會(huì)相同，p1 == p2 時(shí)有兩種情況：
        // 1、要么是兩條鏈表不相交，他倆同時(shí)走到尾部空指針
        // 2、要么是兩條鏈表相交，他倆走到兩條鏈表的相交點(diǎn)
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

5、回文鏈表

尋找回文串

核心思想是從中心向兩端擴(kuò)展

因?yàn)榛匚拇L(zhǎng)度可能為奇數(shù)也可能是偶數(shù)，長(zhǎng)度為奇數(shù)時(shí)只存在一個(gè)中心點(diǎn)，而長(zhǎng)度為偶數(shù)時(shí)存在兩個(gè)中心點(diǎn)，所以上面這個(gè)函數(shù)需要傳入 l 和 r。

// 在 s 中尋找以 s[left] 和 s[right] 為中心的最長(zhǎng)回文串
String palindrome(String s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // 雙指針，向兩邊展開
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 為中心的最長(zhǎng)回文串
    return s.substring(left + 1, right);
}

判斷一個(gè)字符串是不是回文串

因?yàn)榛匚拇菍?duì)稱的，所以正著讀和倒著讀應(yīng)該是一樣的，這一特點(diǎn)是解決回文串問題的關(guān)鍵。

boolean isPalindrome(String s) {
    // 一左一右兩個(gè)指針相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

234. 回文鏈表

給你一個(gè)單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。

這道題的關(guān)鍵在于，單鏈表無法倒著遍歷，無法使用雙指針技巧

1、最簡(jiǎn)單的辦法就是，把原始鏈表反轉(zhuǎn)存入一條新的鏈表，然后比較這兩條鏈表是否相同

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode head2 = reverseList(head);
        while(head2 != null && head != null){
            if(head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

2、其實(shí)，借助二叉樹后序遍歷的思路，不需要顯式反轉(zhuǎn)原始鏈表也可以倒序遍歷鏈表

3、快慢指針，降低空間復(fù)雜度

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 如果fast指針沒有指向null，說明鏈表長(zhǎng)度為奇數(shù)，slow還要再前進(jìn)一步：
        if(fast != null){
            slow = slow.next;
        }
        // 從slow開始反轉(zhuǎn)后面的鏈表，現(xiàn)在就可以開始比較回文串了
        ListNode left = head;
        ListNode right = reverse(slow);
        while(right != null){
            if(left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
    // 迭代反轉(zhuǎn)
    private ListNode reverse(ListNode head){
        ListNode pre = null, next = null, cur = head;
        while (cur != null) {
            next = cur.next;
            // 逐個(gè)結(jié)點(diǎn)反轉(zhuǎn)
            cur.next = pre;
            // 更新指針位置
            pre = cur;
            cur = next;
        }
    // 返回反轉(zhuǎn)后的頭結(jié)點(diǎn)
    return pre;
    }
}

總結(jié)：

首先，尋找回文串是從中間向兩端擴(kuò)展，判斷回文串是從兩端向中間收縮。對(duì)于單鏈表，無法直接倒序遍歷，可以造一條新的反轉(zhuǎn)鏈表，可以利用鏈表的后序遍歷，也可以用棧結(jié)構(gòu)倒序處理單鏈表。

具體到回文鏈表的判斷問題，由于回文的特殊性，可以不完全反轉(zhuǎn)鏈表，而是僅僅反轉(zhuǎn)部分鏈表，將空間復(fù)雜度降到 O(1)。

–end–文章來源地址http://www.zghlxwxcb.cn/news/detail-404940.html

到了這里，關(guān)于LeetCode算法小抄 -- 鏈表(快慢指針、雙指針、回文鏈表)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！