前端也該刷點演算法題——雙指針解“鏈表”題也太香了叭！

来源:https://www.cnblogs.com/bidong/archive/2022/08/31/16644409.html
-Advertisement-
Play Games

雙指針解“鏈表”題也太香了叭！ 同步雙指針 1 查找鏈表中倒數第 k 個節點 劍指Offer22.鏈表中倒數第k個節點 思路： 假設鏈表的長度為n，不難得出倒數第k個節點即為整數第n + 1 - k。 如果一個指針從頭節點開始走k步（頭節點算作第1步），則還需n + 1 - k步才能走完鏈表（到達尾 ...


雙指針解“鏈表”題也太香了叭！

同步雙指針

1 查找鏈表中倒數第 k 個節點

劍指Offer22.鏈表中倒數第k個節點

截屏2022-08-31 14.50.04

思路：

  1. 假設鏈表的長度為n，不難得出倒數第k個節點即為整數第n + 1 - k。

  2. 如果一個指針從頭節點開始走k步（頭節點算作第1步），則還需n + 1 - k步才能走完鏈表（到達尾節點的next，即 null）。

  3. 我們用雙指針，一個指針先走k步，然後兩個指針同時走n + 1 - k步，其中一個指針走完鏈表，另一個指針走到第n + 1 - k個節點處，即倒數第k個節點

代碼

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function (head, k) {
  let p1 = head;
  // 註意此處 i < k - 1，因為 p1 賦值時算作第 1 步
  for (let i = 0; i < k - 1; i++) {
    p1 = p1.next;
  }

  let p2 = head;
  p1 = p1.next; // 同理 p2 賦值算作第 1 步，所以 p1 也要走 1 步
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p2;
};

// 時間複雜度 O(n) n為鏈表長度
// 空間複雜度 O(1)

TS

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function getKthFromEnd(head: ListNode | null, k: number): ListNode | null {
  const dummyHead = new ListNode();
  dummyHead.next = head;
  let p1 = dummyHead;
  for (let i = 0; i < k; i++) {
    p1 = p1.next;
  }

  let p2 = dummyHead;
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p2;
}

// 時間複雜度 O(n) n為鏈表長度
// 空間複雜度 O(1)

註：JS 和 TS 的實現略微有些不同，TS 中添加了一個虛擬頭節點，虛擬頭節點在解決鏈表相關的一些題目時非常有用，體會一下不用虛擬頭節點和使用虛擬頭節點的差別

2 刪除鏈表中倒數第 k 個節點

19.刪除鏈表的倒數第N個結點

截屏2022-08-31 15.22.40

思路

  1. 刪除和查找倒數第 k 個節點的思路大致相同

  2. 唯一的區別是刪除倒數第 k 個節點時我們應該查找倒數第 k + 1 個節點，然後讓其 next 指向 next 的 next。

    因為我們要查找倒數第 k + 1 個節點，所以應該讓第一個指針先走 k + 1 步

  3. 此外刪除的有可能是第 1 個節點，見示例2，此時刪除的是倒數第 1 個節點，所以我們要查找倒數第 2 個節點，然而鏈表總共才 1 個節點，因此我們引入虛擬頭節點來解決

代碼

JS

var removeNthFromEnd = function (head, n) {
  const dummyHead = new ListNode();
  dummyHead.next = head; // 將虛擬頭節點接入鏈表

  let p1 = dummyHead;
  // p1 先走 n + 1 步
  for (let i = 0; i < n + 1; i++) {
    p1 = p1.next;
  }
  let p2 = dummyHead;
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }
  p2.next = p2.next.next;

  // 註意不是返回 head，因為 head 有可能被刪除
  return dummyHead.next;
};

// 時間複雜度 O(n) n為鏈表長度
// 空間複雜度 O(1)

TS

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummyHead = new ListNode();
  dummyHead.next = head;
  let p1 = dummyHead;
  for (let i = 0; i < n + 1; i++) {
    p1 = p1.next;
  }
  let p2 = dummyHead;
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }
  p2.next = p2.next.next;
  return dummyHead.next;
}

註：嘗試不用虛擬頭節點解此題，體會虛擬頭節點的妙處

3 查找兩條鏈表的相交節點

160. 相交鏈表

截屏2022-08-31 16.18.28

思路

  1. 雙指針 p1 和 p2 分別從 headA 和 headB 出發
  2. 如果 p1 走完了鏈表 A，就從 headB 接著走；同理，如果 p2 走完了鏈表 B，就從 headA 接著走
  3. 在這種走法下，p1 和 p2 一定同時走完
  4. 如果兩條鏈表相交，那麼 p1 和 p2 一定會在交點相遇，因為從交點開始到結束點，兩條鏈表的路徑是相同的，於是 p1 和 p2 從結束點向前推能同時到達交點
  5. 如果兩條鏈表不相交，則 p1 和 p2 全程不會相遇

代碼

JS

var getIntersectionNode = function (headA, headB) {
  let p1 = headA;
  let p2 = headB;

  while (p1 || p2) {
    if (p1 === p2) return p1;
    p1 = p1 ? p1.next : headB;
    p2 = p2 ? p2.next : headA;
  }

  return null;
};

// 時間複雜度 O(n + m) m、n 分別為兩條鏈表長度
// 空間複雜度 O(1)

TS

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  let p1 = headA;
  let p2 = headB;

  while (p1 || p2) {
    if (p1 === p2) return p1;
    p1 = p1 ? p1.next : headB;
    p2 = p2 ? p2.next : headA;
  }

  return null;
}

快慢雙指針

1 查找鏈表的中間節點

876. 鏈表的中間結點

截屏2022-08-31 15.42.12

思路

  1. 這題我們讓兩個指針同時走，不過兩個指針的速度不同，分為快慢指針
  2. 我們讓慢指針每次走 1 步，快指針每次走 2 步
  3. 當快指針走完鏈表，即指向 null，慢指針就走到了中間節點的位置

未命名文件 (2)

代碼

JS

var middleNode = function (head) {
  const dummyHead = new ListNode();
  dummyHead.next = head;
  let fastP = dummyHead;
  let slowP = dummyHead;
  while (fastP) {
    slowP = slowP.next;
    fastP = fastP.next;
    fastP && (fastP = fastP.next);
  }
  return slowP;
};

// 時間複雜度 O(n) n 為鏈表長度
// 空間複雜度 O(1)

TS

function middleNode(head: ListNode | null): ListNode | null {
  const dummyHead = new ListNode();
  dummyHead.next = head;
  let fastP = dummyHead;
  let slowP = dummyHead;
  while (fastP) {
    slowP = slowP.next;
    fastP = fastP.next;
    fastP && (fastP = fastP.next);
  }
  return slowP;
}

2 判斷鏈表中是否有環

141. 環形鏈表

截屏2022-08-31 17.16.50

思路

  1. 設定快慢兩指針 fastP 、slowP
  2. fastP 每次走 2 步，slowP 每次走 1 步
  3. 如果鏈表中沒有環，那麼 fastP 最終會先走到 null
  4. 如果鏈表中有環，那麼 fastP 會先進入環，併在環中轉圈
  5. 當 slowP 進入環後，fastP 開始追趕 slowP，最終一定能追上
  6. 當 fastP 追上 slowP 時，若 slowP 走了 n 步，不難得出，fastP 走了 2n 步或 2n - 1 步

代碼

JS

var hasCycle = function (head) {
  // 如果鏈表為空或只有 1 個節點，一定無環
  if (!head || !head.next) return false;

  let slowP = head;
  let fastP = head.next; // slowP 賦值為 head 相當於走了 1 步，故 fastP 要走 2 步
  while (fastP) {
    slowP = slowP.next;
    fastP = fastP.next;
    if (slowP === fastP) return true;
    fastP && (fastP = fastP.next);
  }
  return false;
};

// 時間複雜度 O(n) n 為鏈表長度
// 空間複雜度 O(1)

TS

function hasCycle(head: ListNode | null): boolean {
  if (!head || !head.next) return false;
  let slowP = head;
  let fastP = head.next;
  while (fastP) {
    slowP = slowP.next;
    fastP = fastP.next;
    if (slowP === fastP) return true;
    fastP && (fastP = fastP.next);
  }
  return false;
}

3 查找鏈表中環的入口節點

142. 環形鏈表 II

截屏2022-08-31 19.04.28

思路

  1. 此題和上一題的思路大致相同，不過在上一題的基礎上更進一步
  2. 上一題中提到，如果快指針追上慢指針，且假設 slowP 走了 n 步，不難得出，fastP 走了 2n 步或 2n - 1 步。出現走 2n - 1 步的原因是可能存在 fastP 最後只走 1 步就追上 slowP 的情況
  3. 不過即使規定 fastP 一定要走偶數步，fastP 和 slowP 也一定能在某點相遇，因為在 fastP 走 2 步，slowP 走 1 步的前提下，兩者的間距會 -1，所以最終兩者會相遇
  4. 現在設 slowP 走了 n 步，fastP 走了 2n 步，兩者相遇
  5. 則 fastP 比 slowP 多走了 n 步，這 n 步是環周長的整數倍
  6. 假設 slowP 從環起點開始走了 k 步後，兩者相遇，則從鏈表頭節點開始走 n - k 步（頭節點算第 1 步）就能到達環起點
  7. 而從環起點走 k 步到達相遇點，再走 n - k 步就能到達相遇點，因為從環起點走 k + n - k = n 步回到環起點（見第5點，因為 n 是環周長的整數倍）
  8. 所以我們可以先用快慢指針找到兩者的相遇點，然後讓快指針從頭開始，慢指針從相遇點開始，並且兩者變成同步指針，則兩者再次相遇即為環的起點

代碼

JS

var detectCycle = function (head) {
  if (!head || !head.next) return null;
  let fastP = head.next;
  let slowP = head;
  while (fastP) {
    if (fastP === slowP) break;
    slowP = slowP.next;
    fastP = fastP.next;
    fastP && (fastP = fastP.next);
  }
  if (!fastP) return null;
  fastP = head;
  slowP = slowP.next; // 註意 fastP 賦值為頭節點相當於已經走了 1 步，所以 slowP 也要走 1 步
  while (fastP !== slowP) {
    fastP = fastP.next;
    slowP = slowP.next;
  }
  return fastP;
};

// 時間複雜度 O(n)
// 空間複雜度 O(1)

TS

function detectCycle(head: ListNode | null): ListNode | null {
  // 這裡我們把頭節點當作虛擬節點
  let fastP = head;
  let slowP = head;
  while (fastP) {
    slowP = slowP.next;
    fastP = fastP.next;
    fastP && (fastP = fastP.next);
    if (fastP === slowP) break;
  }
  if (!fastP) return null;
  fastP = head;
  slowP = slowP;
  while (fastP !== slowP) {
    fastP = fastP.next;
    slowP = slowP.next;
  }
  return fastP;
}

註：我們在 TS 中把頭節點當做了虛擬節點，體會兩種解法的細微差別

總結

事實上，使用雙指針的鏈表題還有很多，這裡就舉幾個常見的慄子

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 網卡限速工具之WonderShaper
    GreatSQL社區原創內容未經授權不得隨意使用，轉載請聯繫小編並註明來源。 GreatSQL是MySQL的國產分支版本，使用上與MySQL一致。 什麼是WonderShaper 如何安裝WonderShaper WonderShaper使用幫助 WonderShaper使用示例 查看網卡狀態 限制 ...
  • Jetpack架構組件學習(4)——APP Startup庫的使用
    最近在研究APP的啟動優化,也是發現了Jetpack中的App Startup庫,可以進行SDK的初始化操作,於是便是學習了,特此記錄 原文:Jetpack架構組件學習(4)——App Startup庫的使用 - Stars-One的雜貨小窩 兩種方式初始化SDK 首先,先是講解了關於SDK的初始化 ...
  • 如何通過經緯度坐標獲取附近的地址信息？
    經緯度是確定每個地點位置的精確坐標，使用坐標描述一個位置，非常準確但是並不直觀，面向用戶表達並不友好。HMS Core定位服務提供了逆地理編碼功能，可以通過緯度獲取附近地點的詳細地址，將坐標轉化為地理描述。例如，在電商App的地圖裡標定一個點，就可以顯示具體位置；打車、外賣App里拖動地圖或者點擊地 ...
  • 【面試題】js 問號(?)的強大之處，你知道嗎？？
    問號(?)的強大之處 點擊打開視頻講解更加詳細 一、問號點（?.） obj: { name: "末晨曦吖", }, console.log(this.obj.age, "年齡"); //undefined console.log(this.obj.hobby, "愛好"); //undefined ...
  • 慎用JSON.stringify
    前言 項目中遇到一個 bug，一個組件為了保留一份 JSON 對象，使用 JSON.stringify 將其轉換成字元串，這樣做當然是為了避免對象是引用類型造成數據源的污染。 但發現後面使用 JSON.parse 方法之後，發現數據有所變化。 代碼簡化： let obj = { name: 'Gop ...
  • JSON.stringify() 的妙用
    描述 JSON.stringify()的作用就是把 JavaScript 對象或數組或其他簡單值轉換為字元串。它還可以用於對象的深拷貝；對 JSON 字元串進行格式化（縮進）；在轉換之前對值進行替換操作。 特殊類型的處理 JSON.stringify()遇到函數、日期等類型的值會進行特殊處理。為了讓 ...
  • JavaScript之數組常用API
    ####這篇文章主要幫助大家簡單理解數組的一些常用API用法，許多小伙伴常用方法記不住？別急，看完下麵的介紹您一定就會明白各個方法是如何用的了😘。該文章適合新手小白看,大佬可以多多指點❤️! 1.數組的創建以及Array.of() 下麵介紹幾種創建數組的方法： // 創建數組的三種方式 // 1. ...
  • Web端CAD圖形找不同？一鍵在Web端找出CAD圖不同並對比分析
    引言 在實際中，當多專業設計協助時，遇到圖紙更新後，要對比圖紙找出圖紙的不同處，一直是一個比較耗時費力的事情，也是業內的一大痛點。一般CAD新舊圖紙的內容對比，包括增加新的圖形元素、減少原有的圖形元素以及對原有的圖形進行修改。傳統的方式一般是在PC端CAD環境中實現對圖紙比較的功能，然後隨著互聯網移 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類