Java鍊錶實例分析
1、刪除值為val的所有節點
刪除鍊錶中等於給定值val的所有節點。 【OJ連結】
定義兩個指標prev、cur,cur指向頭節點的下一個節點,prev總是指向cur的前一個結點(方便刪除節點)。透過cur指標去遍歷鍊錶,和val值比較,相同就刪除這個節點。最後再來比較頭節點。
/** * 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 removeElements(ListNode head, int val) { if(head==null){ return null; } ListNode prev=head; ListNode cur=head.next; while(cur!=null){ if(cur.val==val){ prev.next=cur.next; cur=cur.next; }else{ prev=cur; cur=cur.next; } } if(head.val==val){ head=head.next; } return head; } }
2、反轉鍊錶
反轉一個鍊錶。 【OJ連結】
在遍歷鍊錶時,將目前節點的 指標改為指向前一個節點。由於節點沒有引用其前一個節點,因此必須事先儲存其前一個節點。在更改引用之前,還需要儲存後一個節點。最後返回新的頭引用。
/** * 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) { if(head==null){ return null; } ListNode cur=head.next; head.next=null; while(cur!=null){ ListNode curNext=cur.next; cur.next=head; head=cur; cur=curNext; } return head; } }
3、返回鍊錶中間節點
給定一個帶有頭節點的非空單鍊錶,傳回鍊錶的中間節點。如果有兩個中間節點,則傳回第二個中間節點。 【OJ連結】
我們可以定義兩個快慢指標(fast、slow),都指向頭節點。快指針每次走兩步,慢指針每次走一步。鍊錶有偶數個節點時,fast=null時slow為中間節點;鍊錶有奇數個節點時,fast.next=null時slow為中間節點。
/** * 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) { if(head==null){ return null; } ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } return slow; } }
4、傳回鍊錶第K個節點
#輸入一個鍊錶,回傳該鍊錶中倒數第K個節點。 【OJ連結】
這個題和找中間節點的想法相似。定義兩個指標(fast、slow)。在K合理的前提下,我們可以讓快指標先走K-1步,然後快慢指標同時向後走,當fast到達鍊錶結尾時,slow就指向倒數第K個節點。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(k<=0||head==null){ return null; } ListNode fast=head; ListNode slow=head; while(k-1>0){ if(fast.next==null){ return null; } fast=fast.next; //先让快节点走k-1步 k--; } while(fast.next!=null){ fast=fast.next; slow=slow.next; } return slow; } }
5、合併有序鍊錶
將兩個有序鍊錶合併為一個有序鍊錶並傳回。新鍊錶是透過拼接給定的兩個鍊錶的所有節點組成的。 【OJ連結】
解這個題,需要定義假節點來充當新鍊錶的頭節點。透過兩個鍊錶的頭節點去遍歷兩個節點,去比較兩個鍊錶對應節點的值,將值小的節點連接到新鍊錶的後面,知道兩個鍊錶遍歷完,當其中一個鍊錶為空時,直接將另一個鍊錶連接到新鍊錶後面即可。
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1==null){ return list2; } if(list2==null){ return list1; } //创建虚拟节点,充当新链表的头节点,值不代表任何意义 ListNode node=new ListNode(-1); ListNode cur=node; while(list1!=null&&list2!=null){ if(list1.val<list2.val){ cur.next=list1; list1=list1.next; }else{ cur.next=list2; list2=list2.next; } cur=cur.next; } if(list1==null){ cur.next=list2; }else{ cur.next=list1; } return node.next; } }
6、以值分割鍊錶
將一個鍊錶依照給定值X分成兩個部分,所有小於X的節點排在大於或等於X的節點之前。不改變節點原來的順序。 【OJ連結】
首先我們需要定義四個指標(bs、be、as、ae)分別表示小於X部分鍊錶的頭節點和尾節點、大於X部分鍊錶的頭節點和尾節點。透過頭節點遍歷鍊錶,將鍊錶分為兩部分。最後將兩個鍊錶連接起來即可。需要特別注意,當小於X部分鍊錶不為空時,我們需要手動將ae.next置為空。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { if(pHead==null){ return null; } ListNode bs=null; ListNode be=null; ListNode as=null; ListNode ae=null; ListNode cur=pHead; while(cur!=null){ if(cur.val<x){ if(bs==null){ bs=cur; be=cur; }else{ be.next=cur; be=cur; } }else{ if(as==null){ as=cur; ae=cur; }else{ ae.next=cur; ae=cur; } } cur=cur.next; } if(bs==null){ return as; //如果小于X部分为空,则直接返回大于X部分即可。此时ae.next一定为null } be.next=as;//否则连接小于X和大于X部分 if(as!=null){ ae.next=null; //当小于X部分不为空时,ae.next可能不为null,需要手动置为null } return bs; } }
7、判讀回文鍊錶
#判斷鍊錶是不是回文鍊錶。 【OJ連結】
首先我們需要找到鍊錶的中間節點,然後將後半段鍊錶反轉。最後透過兩邊逐步比較即可。特別注意,當鍊錶結點個數為偶數時,因為中間節點的緣故,兩邊遍歷時,無法相遇,需要特殊處理。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class PalindromeList { public boolean chkPalindrome(ListNode A) { if(A==null){ return false; } if(A.next==null){ return true; } //求链表的中间节点 ListNode slow=A; ListNode fast=A; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //反转后半段链表 ListNode cur=slow.next; while(cur!=null){ ListNode curNext=cur.next; cur.next=slow; slow=cur; cur=curNext; } //判断回文链表 while(slow!=A){ if(slow.val!=A.val){ return false; } if(A.next==slow){ return true; } slow=slow.next; A=A.next; } return true; } }
8、找兩個鍊錶的公共節點
輸入兩個鍊錶,輸出兩個鍊錶的第一個公共節點。沒有回傳NULL。 【OJ連結】
兩個鍊錶相交呈現Y字型。那麼兩個鍊錶長度的差肯定是未相交前兩個鍊錶節點的差。我們需要求出兩個鍊錶的長度。定義兩個指標(pl、ps),讓pl指向長的鍊錶,ps指向短的鍊錶。求兩個鍊錶的長度差len。讓pl想走len步。這樣兩個鍊錶的剩餘長度就相同。此時兩個指標同時遍歷連個鍊錶,如果其指向一致,則兩個鍊錶相交,否則,兩個鍊錶不相交。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { //求链表长度 public int len(ListNode head){ int len=0; while(head!=null){ head=head.next; len++; } return len; } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null||headB==null){ return null; } ListNode pl=headA; ListNode ps=headB; int lenA=len(headA); int lenB=len(headB); int len=lenA-lenB; if(len<0){ //pl指向长的链表,ps指向短的链表 pl=headB; ps=headA; len=-len; } while(len--!=0){ pl=pl.next; } while(pl!=null){ if(pl==ps){ return pl; } pl=pl.next; ps=ps.next; } return null; } }
9、判斷成環鍊錶
判斷鍊錶中是否有環。 【OJ連結】
還是快慢指標。慢指針一次走一步,快指針一次走兩步。兩個指標從鍊錶起始位置開始運作。如果鍊錶帶環則一定會在環中相遇,否則快指針率先走到鍊錶的末端。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null){ return false;//链表为空或者只有一个节点时,没有环 } ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ return true; //如果快慢节点可以相遇,表示链表有环 } } return false; } }
10、返回成環鍊錶的入口
給定一個鍊錶,判斷鍊錶是否有環並回傳入環的節點。如果沒有環,則回傳NULL。 【OJ連結】
让一个指针从链表的其实在位置开始遍历,同时另一个指针从上题中两只真相与的位置开始走,两个指针再次相遇时的位置肯定为环的入口
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { //判断链表是否有环,并返回第一次快慢节点相交的位置 public ListNode hasCycle(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){ return slow; } } return null; } //当返回的结点与头节点再次相交时,为环的入口 public ListNode detectCycle(ListNode head) { ListNode node=hasCycle(head); if(node==null){ return null; }else{ while(head!=node){ head=head.next; node=node.next; } } return head; } }
以上是Java鍊錶實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

膠囊是一種三維幾何圖形,由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下: 膠囊體積 = 圓柱體體積 兩個半球體體積 其中, r: 半球體的半徑。 h: 圓柱體的高度(不包括半球體)。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積: 體積 = π × r2 × h (4

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

Java是熱門程式語言,適合初學者和經驗豐富的開發者學習。本教學從基礎概念出發,逐步深入解說進階主題。安裝Java開發工具包後,可透過建立簡單的「Hello,World!」程式來實踐程式設計。理解程式碼後,使用命令提示字元編譯並執行程序,控制台上將輸出「Hello,World!」。學習Java開啟了程式設計之旅,隨著掌握程度加深,可創建更複雜的應用程式。

Spring Boot簡化了可靠,可擴展和生產就緒的Java應用的創建,從而徹底改變了Java開發。 它的“慣例慣例”方法(春季生態系統固有的慣例),最小化手動設置
