前端程式員學好演算法系列(四)鏈表

来源:https://www.cnblogs.com/kbnet/archive/2020/07/26/13382656.html

24. 兩兩交換鏈表中的節點給定一個鏈表,兩兩交換其中相鄰的節點,並返回交換後的鏈表。 你不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。 示例: 給定 1->2->3->4, 你應該返回 2->1->4->3. 解題:我們定義4個指針如上進行節點交換,1.給head添加一個虛擬頭節點t ...


24. 兩兩交換鏈表中的節點
給定一個鏈表,兩兩交換其中相鄰的節點,並返回交換後的鏈表。

你不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。

示例:

給定 1->2->3->4, 你應該返回 2->1->4->3.


解題:我們定義4個指針如上進行節點交換,
1.給head添加一個虛擬頭節點thead
2.定義4個指針 p, node1, node2, next 我們需要將p.next ->node2  node1.next -> next    node2.next ->node1        完成以後將 p指針移動到node1
3.我們需要判斷 p.next 和p.next.next 都不為空,這樣next 最差為null 不會越界

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let thead = new ListNode(0);
    thead.next = head;
    let p = thead;
    while(p.next != null && p.next.next != null){
        let node1 = p.next;
        let node2 = node1.next;
let next = node2.next
        p.next = node2;
        node1.next = next;
        node2.next = node1;
        p = node1;
    }
    return thead.next;
};

237. 刪除鏈表中的節點
請編寫一個函數,使其可以刪除某個鏈表中給定的(非末尾)節點,你將只被給定要求被刪除的節點。

現有一個鏈表 -- head = [4,5,1,9],它可以表示為:

 

示例 1:

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節點,那麼在調用了你的函數之後,該鏈表應變為 4 -> 1 -> 9.

解題:

1.我們無法直接刪除給定的節點,我們只能拿到給定節點的下一個節點的值,

2.我們用該節點的下一個節點的值覆蓋當前節點的值,然後刪除下一個節點,即相當於實現了對該節點的刪除

3.我們處理node 為null和node.next為null的特殊情況

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
     if(node == null){
        return
     }
     if(node.next == null){
          delete node
          node = null
          return
     }
     node.val = node.next.val
     node.next = node.next.next
};

19. 刪除鏈表的倒數第N個節點
給定一個鏈表,刪除鏈表的倒數第 n 個節點,並且返回鏈表的頭結點。

示例:

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數第二個節點後,鏈表變為 1->2->3->5.

解題:
1.給head設置虛擬頭節點
2.設置fast 和show兩個指針
3.fast指針先移動n位,然後fast指針和show指針同時移動
4.當fast指針為空時,show.next節點即為需要刪除的節點,我們把show.next ->show.next.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // 快先走 n+1 步
    while(n--) {
        fast = fast.next
    }
    let i = 0
    // fast、slow 一起前進
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next
        
    }
    slow.next = slow.next.next
    return preHead.next
};

鏈表的js演算法就先介紹到這裡了

 


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

更多相關文章
  • 1.在linux系統下安裝跨系統傳輸文件工具 root用戶下 根目錄輸入 yum -y install lrzsz 2.把apache-jmeter-4.0zip包 用rz命令上傳到linux系統的根目錄下 解壓 3.配置jmeter環境變數 vim /etc/profile 添加 export P ...
  • 西北望鄉何處是,東南見月幾回圓。 月亮又慢悠悠的掛上了天空,趁著睡前夢囈,我就帶領各位可愛的讀者們探索MySql最後的子查詢部分。 說明:有些查詢結果出來結果截圖與題目要求不一樣會出現多餘的欄位是為了方便展示結果的可讀性。實際操作的讀者可以刪除SELECT後面多餘的欄位得到正確的結果。 #WHERE ...
  • Redis是什麼?redis是一款基於BSD協議,開源的非關係型資料庫(nosql資料庫),作者是義大利開發者Salvatore Sanfilippo在2009年發佈,使用C語言編寫;redis是基於記憶體存儲,而且是目前比較流行的鍵值資料庫(key-value database),它提供將記憶體通過... ...
  • MariaDB 資料庫管理系統是 MySQL 的一個分支,主要由開源社區在維護,採用 GPL 授權許可。開發這個分支的原因之一是:甲骨文公司收購了 MySQL 後,有將 MySQL 閉源的潛在風險,因此社區採用分支的方式來避開這個風險。MariaDB完全相容mysql,使用方法也是一樣的。 系統環境 ...
  • 參考:https://juejin.im/entry/58b93af3ac502e006c0820c9 1.常見的加密方式:Base64、MD5、AES、EDS、RSA HTTPS 以及SSL/TSL 什麼是SSL?SSL(Secure Sockets Layer, 安全套接字層),因為原先互聯網上 ...
  • 1.棧的基礎使用,js中數組直接可以作為棧使用,棧遵循先進後出的原則,即js可以使用push()和pop() 比較容易的實現一個棧 20. 有效的括弧給定一個只包括 '(',')','{','}','[',']' 的字元串,判斷字元串是否有效。 有效字元串需滿足: 左括弧必須用相同類型的右括弧閉合。 ...
  • (一)單一 |【1】屬性選擇器 | | | | | | | |p[alt]|選擇具有att屬性的 |p元素 | |p[alt="val"] |選擇att屬性值 |等於val的p | |p[alt^="val"] |匹配att屬性值 |以val開頭的p | |p[alt$="val"] |匹配att屬 ...
  • 美拍短視頻按作者批量下載,去水印的方法教程,很多做自媒體搬運或者要下載美拍短視頻上面的素材,都需要批量下載美拍無水印短視頻。這裡教大家如何按作者批量下載美拍無水印短視頻,並自動修改MD5消重。此文分享的是一個線上的網站工具,不需要下載任何軟體,直接在瀏覽器里打開工具網址就可以使用的。 其實不僅僅是支 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...