【數據結構_5】鏈表（模擬實現以及leetcode上鏈表相關的題目）

書接上文，繼續編寫鏈表的功能

4.鏈表的中間插入

在鏈表中，本身是沒有下標這樣的概念的，不像順序表，順序表根據下標訪問元素，O(1)復雜度。鏈表需要遍歷之后找到正確的位置才能進行插入，為O（N）復雜度。

但是這件事在JAVA中是個例外，JAVA標準庫LinkedList引入了下標概念。

    public int size(){int size =0;for(Node cur = head; cur.next!=null;cur = cur.next){size++;}return size;}//4.中間插入的操作public void add(int index,String value){int size = size();//1.首先判斷index是否合法if(index<0 || index >size){throw  new RuntimeException("下標超出范圍");}//1.首先要找到index-1的prev節點Node prev = head;//上述代碼出現了一個問題：如果是頭插，那么就會導致循環無法進去，那么prev是第一個節點，插入的永遠是下標為1的地方//*特殊情況需要特殊考慮if(index ==0){addFirst(value);return;}for (int i = 0; i < index-1; i++) {prev = prev.next;}//3.此時進行修改操作Node newNode = new Node(value);newNode.next = prev. next;prev.next = newNode;}
//5.看某個元素是否被包含在鏈表當中
 public boolean contains(String value){for(Node cur = head;cur.next != null;cur = cur.next){if(cur.value.equals(value)){return true;}}return false;}

//6.找到了就返回index
 public int indexOf(String value){int index =0;for(Node cur = head;cur.next != null;cur = cur.next){if(cur.value.equals(value)){return index;}else {index++;}}return -1;}
//7.根據下標刪除

    //7.根據下標刪除public void remove( int index){int size = size();//1.首先要判斷index的值是否合法if( index <0 || index >=size){throw new RuntimeException("下標越界");}//*要考慮特殊的刪除頭節點if(index ==0){head = head.next;return ;}//2.其次要找到上一個節點Node prev = head;for (int i = 0; i < index-1; i++) {prev = prev.next;}//3.然后要進行刪除操作prev.next = prev.next.next;}

//8.根據值來刪除
    public void remove(String value){//還要考慮空鏈表的情況if(head == null){return;}//有關添加刪除操作都要考慮前一個節點 所以每次創建的都是prevNode prev = head;for(;prev!=null;prev= prev.next){if(prev.next!= null&&prev.next.equals(value)){//找到了break;}}//出來之后有兩種情況 一種是找到了value 另一種是遍歷完了都沒有找到valueif(prev == null){return;}else{//找到了，進行刪除操作Node cur = prev.next;prev.next = cur.next;}}

//9.全部刪除的clear操作

    //9.clear()public void clear(){head = null;}

至此，LinkedList基本寫成了

總體：

package LinkedList;//要想實現鏈表的基本功能，首先要表示鏈表的一個節點
//對于節點這個類來說，他的本身功能單一，比較簡單
//如果高一些get set 方法 ，后續代碼就會顯得很難看class Node{public String value;//節點保存的值public Node next;//這個節點的下一個元素public Node(String value) {this.value = value;this.next = null;}//當我們創建一個Node的時候，就創建好了鏈表的頭節點，此時鏈表頭節點的值可以確定，且尚未含有下一個節點
}
//這是一個單鏈表的節點 雙向鏈表還需要一個prev
public class MyLinkedList {//把鏈表的頭節點表示出來，此時整個鏈表就都能被獲取到了//此處不包含傀儡系欸但，head== null 的時候表示空的鏈表private Node head = null;//1.鏈表的頭插操作public void addFirst(String value){Node newNode = new Node(value);newNode.next =head;head = newNode;//head只是一個引用類型！！！}//2.遍歷鏈表的操作public String toString(){StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (Node cur = head;cur!= null; cur= cur.next) {stringBuilder.append(cur.value);if(cur.next!= null) {stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();}//3.尾插操作public void addLast( String value){//1.首先找到最后一個節點Node tail = head;//*還要考慮特殊的情況if(head == null){Node node = new Node(value);head = node;return;}for (;tail.next!=null; tail = tail.next) {if(tail.next==null){break;}}//此時的tail也就是我們要找的最后一個節點Node node = new Node(value);tail.next = node;node.next = null;}public int size(){int size =0;for(Node cur = head; cur.next!=null;cur = cur.next){size++;}return size;}//4.中間插入的操作public void add(int index,String value){int size = size();//1.首先判斷index是否合法if(index<0 || index >size){throw  new RuntimeException("下標超出范圍");}//1.首先要找到index-1的prev節點Node prev = head;//上述代碼出現了一個問題：如果是頭插，那么就會導致循環無法進去，那么prev是第一個節點，插入的永遠是下標為1的地方//*特殊情況需要特殊考慮if(index ==0){addFirst(value);return;}for (int i = 0; i < index-1; i++) {prev = prev.next;}//3.此時進行修改操作Node newNode = new Node(value);newNode.next = prev. next;prev.next = newNode;}//5.看某個元素是否被包含在鏈表當中public boolean contains(String value){for(Node cur = head;cur != null;cur = cur.next){if(cur.value.equals(value)){return true;}}return false;}//6.找到了就返回indexpublic int indexOf(String value){int index =0;for(Node cur = head;cur != null;cur = cur.next){if(cur.value.equals(value)){return index;}else {index++;}}return -1;}//7.根據下標刪除public void remove( int index){int size = size();//1.首先要判斷index的值是否合法if( index <0 || index >=size){throw new RuntimeException("下標越界");}//*要考慮特殊的刪除頭節點if(index ==0){head = head.next;return ;}//2.其次要找到上一個節點Node prev = head;for (int i = 0; i < index-1; i++) {prev = prev.next;}//3.然后要進行刪除操作prev.next = prev.next.next;}//8.根據值來刪除public void remove(String value){//還要考慮空鏈表的情況if(head == null){return;}//有關添加刪除操作都要考慮前一個節點 所以每次創建的都是prevNode prev = head;for(;prev!=null;prev= prev.next){if(prev.next!= null&&prev.next.equals(value)){//找到了break;}}//出來之后有兩種情況 一種是找到了value 另一種是遍歷完了都沒有找到valueif(prev == null){return;}else{//找到了，進行刪除操作Node cur = prev.next;prev.next = cur.next;}}//9.clear()public void clear(){head = null;}
}
class Solution {public ListNode removeElements(ListNode head, int val) {//1.首先判斷鏈表是否為空if(head == null){return null;}//2.利用循環刪除每一個值為val的元素，但是是從head后面開始刪除的！ListNode prev = head;ListNode cur = prev.next;while(cur!=null){if(cur.val == val){//就觸發刪除操作prev.next = cur.next;//還要將cur進行后置cur = prev.next;}else{prev = cur;cur =cur.next;}}//cur == null 再判定開頭的元素if(head.val==val){head = head.next;}return head;}}

1.這道題的要點就在于頭節點的刪除，如果head=[7,7,7,7]，我們就先不管頭節點，先把后面值等于val的節點刪除，然后循環出來再去考慮頭節點。

現在要得到這個鏈表的翻轉鏈表

思路：分別設置三個引用變量：prev,cur,next。使三者遍歷整個鏈表，按照如下圖所示的操作完成鏈表的翻轉。

*為什么一定要設置三個，而不能只使用cur？

因為在完成翻轉操作之后，我們還想讓循環繼續，但是此時cur.next=prev，所以我們要通過next這個引用變量為我們指明前方的道路

也就是說，pev=cur;cur = next; next = next.next;

一直到cur?== null,然后跳出循環

class Solution {public ListNode reverseList(ListNode head) {//1.首先判斷鏈表是否為空if(head == null){return null;}   //2.如果鏈表里只含有一個元素，那么翻轉還是不反轉沒有任何影響if(head.next == null){return head;}//3.來處理一般情況//首先要創建三個引用變量ListNode prev = null;ListNode cur = head;ListNode next = cur.next;//再創建一個新的頭節點，待會兒返回ListNode newHead = null;while(cur!=null){next = cur.next;if(next == null){//已經全部完成了newHead = cur;//這個地方不能break，因為下面的操作還需要更新！！！}cur.next = prev;prev = cur;cur = next;}

思路：首先我們可以計算處鏈表的長度，其次只要將鏈表的長度/2 之后再遍歷我們就可以得到第二個中間節點的值了

class Solution {public ListNode middleNode(ListNode head) {int size = 0;for(ListNode cur = head ; cur!= null;cur = cur.next){size++;}int num = size/2;ListNode cur = head;while(num != 0){num--;cur = cur.next;}return cur;}
}

思路：1.創建新的鏈表表示最終結構

2.搞兩個引用，分別指向兩個鏈表

3.比較這兩個引用的值，誰小，就把哪個節點取出來，插入到新鏈表的末尾，如果這兩個引用，有任何一個指向了null，說明該鏈表就結束了，就把另一個鏈表剩余的元素都添加到新鏈表的末尾即可。

代碼：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//1.判斷list1為空鏈表的情況if(list1 == null){return list2;}//2。判斷list2為空鏈表的情況if(list2 == null){return list1;}//3.考慮一般情況//為了使后續的插入方便我們首先創建一個傀儡節點以及末尾節點ListNode newHead = new ListNode(0);ListNode tail = newHead;ListNode cur1 = list1;ListNode cur2 = list2;while(cur1!=null && cur2 !=null){if(cur1.val < cur2.val){//cur1比較小 所以把cur1放進來ListNode newNode =cur1;tail.next = newNode;tail = newNode; cur1 = cur1.next;}else{ListNode newNode =cur2;tail.next = newNode;tail = newNode; cur2 = cur2.next;}}//出來的時候，要么cur1還有剩余，要么cur2還有剩余if(cur1 != null){//把剩余的鏈表給他接上去tail.next = cur1;}if(cur2 != null){tail.next = cur2;}return newHead.next;//不能返回newHead 要返回傀儡節點的下面一個節點}
}

寫不動了！明天再見！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/901294.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/901294.shtml
英文地址，請注明出處：http://en.pswp.cn/news/901294.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C語言的發展史

C語言的發展史

一、起源 C語言的起源可以追溯到20世紀60年代末期。其前身是BCPL&#xff08;Basic Combined Programming Language&#xff09;語言&#xff0c;由劍橋大學的Martin Richards于1967年在CPL語言的基礎上簡化而來。1970年&#xff0c;美國貝爾實驗室的Ken Thompson以BCPL語言為…
閱讀更多...
深入解析棧式虛擬機與反向波蘭表示法

深入解析棧式虛擬機與反向波蘭表示法

1.1 什么是虛擬機&#xff1f; 虛擬機&#xff08;Virtual Machine, VM&#xff09;是一種軟件實現的計算機系統&#xff0c;提供與物理計算機相類似的環境&#xff0c;但在軟件層面運行。虛擬機的存在簡化了跨平臺兼容性、資源管理以及安全隔離等問題。 1.2 棧式虛擬機的架構…
閱讀更多...
ubuntu 系統安裝Mysql

ubuntu 系統安裝Mysql

安裝 mysql sudo apt update sudo apt install mysql-server 啟動服務 sudo systemctl start mysql 設置為開機自啟 sudo systemctl enable mysql 查看服務狀態 &#xff08;看到類似“active (running)”的狀態信息代表成功&#xff09; sudo systemctl status mysql …
閱讀更多...
《前端面試題之 CSS篇（第一集）》

《前端面試題之 CSS篇（第一集）》

目錄 1、CSS的盒模型2、CSS選擇器及其優先級3、隱藏元素的方法有那些4、px、em、rem的區別及使用場景5、重排、重繪有什么區別6、水平垂直居中的實現7、CSS中可繼承與不可繼承屬性有哪些8、Sass、Less 是什么&#xff1f;為什么要使用他們&#xff1f;9、CSS預處理器/后處理器是…
閱讀更多...
HTTP：四.HTTP連接

HTTP：四.HTTP連接

HTTP（Hypertext Transfer Protocol）是一種用于傳輸超文本數據的應用層協議。它是互聯網上最常用的協議，用于在客戶端和服務器之間傳輸數據。HTTP協議通常用于從Web服務器傳輸網頁和文件到客戶端瀏覽器，并支持其他用途，如傳輸API數據和傳輸文件。 HTTP連接是指客戶端向服務…
閱讀更多...
opencv 識別運動物體

opencv 識別運動物體

import cv2 import numpy as npcap cv2.VideoCapture(video.mp4) try:import cv2backSub cv2.createBackgroundSubtractorMOG2() except AttributeError:backSub cv2.bgsegm.createBackgroundSubtractorMOG()#形態學kernel kernel cv2.getStructuringElement(cv2.MORPH_REC…
閱讀更多...
要查看 ??指定 Pod 的資源限制（CPU/內存）

要查看 ??指定 Pod 的資源限制（CPU/內存）

要查看 指定 Pod 的資源限制&#xff08;CPU/內存&#xff09;&#xff0c;可以通過以下 kubectl 命令實現&#xff1a; 1. 快速查看某個 Pod 的資源限制 kubectl get pod <pod-name> -o jsonpath{.spec.containers[*].resources} | jq輸出示例&#xff1a; {"lim…
閱讀更多...
信息安全管理與評估廣東省2023省賽正式賽題

信息安全管理與評估廣東省2023省賽正式賽題

任務1&#xff1a;網絡平臺搭建(60分) 題號 網絡需求 1 根據網絡拓撲圖所示&#xff0c;按照IP地址參數表&#xff0c;對DCFW的名稱、各接口IP地址進行配置。&#xff08;10分&#xff09; 2 根據網絡拓撲圖所示&#xff0c;按照IP地址參數表&#xff0c;對DCRS的名稱進…
閱讀更多...
IBM Rational Software Architect安裝感受及使用初體驗

IBM Rational Software Architect安裝感受及使用初體驗

1 安裝感受 最近準備用UML 2.0繪制模型圖。在讀UML創始人之一Grady Booch寫的書《Object-Oriented Analysis and Design with Applications》&#xff08;第3版&#xff09;1時&#xff0c;發現書中用的UML工具之一為IBM Rational Software Architect&#xff08;RSA&#xff…
閱讀更多...
接聽電話，手機靠近耳朵后拿開，掛斷電話，設備自動鎖屏

接聽電話，手機靠近耳朵后拿開，掛斷電話，設備自動鎖屏

目錄 一、問題分析/需求分析 二、解決方案 一、問題分析/需求分析 先說一下大致流程： 首先是打電話過程會啟動PROXIMITY（接近光傳感器）用于監聽手機是否到耳邊，當手機到耳邊時進行滅屏處理，滅屏過程中會調用到鎖屏，所以最終會導致鎖屏 詳細流程分析： 首先根據日志看…
閱讀更多...
21天Python計劃：零障礙學語法（更新完畢）

21天Python計劃：零障礙學語法（更新完畢）

目錄 序號標題鏈接day1Python下載和開發工具介紹https://blog.csdn.net/XiaoRungen/article/details/146583769?spm1001.2014.3001.5501day2數據類型、字符編碼、文件處理https://blog.csdn.net/XiaoRungen/article/details/146603325?spm1011.2415.3001.5331day3基礎語法與…
閱讀更多...
Honor of Kings (S39) 13-win streak

Honor of Kings (S39) 13-win streak

Honor of Kings (S39) 13-win streak S39賽季13連勝&#xff0c;莊周&#xff0c;廉頗硬輔助&#xff0c;對面有回血就先出紅蓮斗盆&#xff0c;有遇到馬克沒帶凈化的&#xff0c;出【冰霜沖擊】破他大招 S39&#xff0c;莊周廉頗前排硬輔助全肉全堆血13連勝_嗶哩嗶哩bilibi…
閱讀更多...
AI技術實戰：從零搭建圖像分類系統全流程詳解

AI技術實戰：從零搭建圖像分類系統全流程詳解

AI技術實戰&#xff1a;從零搭建圖像分類系統全流程詳解 人工智能學習 https://www.captainbed.cn/ccc 前言 本文將以圖像分類任務為切入點&#xff0c;手把手教你完成AI模型從數據準備到工業部署的全鏈路開發。通過一個完整的Kaggle貓狗分類項目&#xff08;代碼兼容PyTorch…
閱讀更多...
NIPS2024論文 End-to-End Ontology Learning with Large Language Models

NIPS2024論文 End-to-End Ontology Learning with Large Language Models

文章所謂的端到端本體學習&#xff0c;指的是從輸入到目標本體這個完整過程。在很多其他文章中&#xff0c;是把本體學習這個任務肢解了來做的&#xff0c;同樣也是肢解了之后評估。 文章號稱的貢獻&#xff0c;不但對通用本體學習提供所謂的baseline&#xff0c;而且還給出了驗…
閱讀更多...
【NLP】18. Encoder 和 Decoder

【NLP】18. Encoder 和 Decoder

1. Encoder 和 Decoder 概述 在序列到序列&#xff08;sequence-to-sequence&#xff0c;簡稱 seq2seq&#xff09;的模型中&#xff0c;整個系統通常分為兩大部分&#xff1a;Encoder&#xff08;編碼器&#xff09;和 Decoder&#xff08;解碼器&#xff09;。 Encoder&…
閱讀更多...
Deepseek Bart模型相比Bert的優勢

Deepseek Bart模型相比Bert的優勢

BART&#xff08;Bidirectional and Auto-Regressive Transformers&#xff09;與BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;雖然均基于Transformer架構&#xff0c;但在模型設計、任務適配性和應用場景上存在顯著差異。以下是BART…
閱讀更多...
在人工智能與計算機技術融合的框架下探索高中教育數字化教學模式的創新路徑

在人工智能與計算機技術融合的框架下探索高中教育數字化教學模式的創新路徑

一、引言 1.1 研究背景 在數字中國戰略與《中國教育現代化 2035》的政策導向下&#xff0c;人工智能與計算機技術的深度融合正深刻地重構著教育生態。隨著科技的飛速發展&#xff0c;全球范圍內的高中教育都面臨著培養具備數字化素養人才的緊迫需求&#xff0c;傳統的教學模式…
閱讀更多...
深度探索 C 語言：指針與內存管理的精妙藝術

深度探索 C 語言：指針與內存管理的精妙藝術

C 語言作為一門歷史悠久且功能強大的編程語言&#xff0c;以其高效的性能和靈活的底層控制能力&#xff0c;在計算機科學領域占據著舉足輕重的地位。 指針和內存管理是 C 語言的核心特性&#xff0c;也是其最具挑戰性和魅力的部分。深入理解指針與內存管理&#xff0c;不僅能夠…
閱讀更多...
QQ郵箱授權碼如何獲取 QQ郵箱授權碼獲取方法介紹

QQ郵箱授權碼如何獲取 QQ郵箱授權碼獲取方法介紹

QQ郵箱授權碼如何獲取 QQ郵箱授權碼獲取方法介紹 https://app.ali213.net/gl/857287.html
閱讀更多...
jupyter4.4安裝使用

jupyter4.4安裝使用

一、chrome谷歌瀏覽器 1. 安裝 1.1 下載地址&#xff1a; 下載地址&#xff1a; https://www.google.cn/intl/zh-CN_ALL/chrome/fallback/ 2 插件markdown-viewer 2.1 下載地址&#xff1a; 下載地址&#xff1a;https://github.com/simov/markdown-viewer/releases 2.2…
閱讀更多...
最新文章

Copyright @ 2022~2023