關于 Java 的數(shù)據(jù)結(jié)構(gòu)鏈表
更新時間：2021年09月06日 15:42:38 作者：吞吞吐吐大魔王
這篇文章主要介紹了關于 Java 的數(shù)據(jù)結(jié)構(gòu)鏈表的相關資料,需要的朋友可以參考下面文章內(nèi)容
數(shù)據(jù)結(jié)構(gòu)關于 Java 的鏈表
1. 刪除鏈表中等于給定值 val 的所有節(jié)點
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){
cur=cur.next;
prev.next=cur;
}else{
prev=cur;
cur=cur.next;
}
}
if(head.val==val){
head=head.next;
}
return head;
}
}
2. 反轉(zhuǎn)一個單鏈表
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode cur=head;
ListNode newHead=null;
while(cur!=null){
ListNode curNext=cur.next;
cur.next=newHead;
newHead=cur;
cur=curNext;
}
return newHead;
}
}
方法： 頭插法（從第二個節(jié)點開始對第一個節(jié)點進行頭插）
注意：
- 逆置不是只將數(shù)值反轉(zhuǎn)，而是將節(jié)點本身進行逆置
- 如果用前一章的 diplay 方法將逆置后的打印結(jié)果不正確，因為該 diplay 方法是從一開始定義的 head 節(jié)點開始打印，而現(xiàn)在真正的頭節(jié)點已經(jīng)改變，可以將其修改一下
public void display2(Node newHead){ Node cur = newHead; while(cur!=null){ System.out.print(cur.val + " "); cur=cur.next; } System.out.println(); }
3. 給定一個帶有頭結(jié)點 head 的非空單鏈表
給定一個帶有頭結(jié)點 head 的非空單鏈表，返回鏈表的中間結(jié)點。如果有兩個中間結(jié)點，則返回第二個中間結(jié)點
方法一：通過遍歷找到節(jié)點數(shù)，然后找到中間節(jié)點
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null){
return null;
}
ListNode cur=head;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
count=count/2+1;
ListNode node=head;
int i=0;
while(i!=count-1){
node=node.next;
i++;
}
return node;
}
}
方法二： 快慢指針法（快指針一次走兩步，慢指針一次走一步）
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
4. 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點
方法一：通過遍歷找到節(jié)點數(shù)，然后找到倒數(shù)第 k 個節(jié)點
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return null;
}
ListNode cur = head;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
if(k<1 || k>count){
return null;
}
ListNode node = head;
int i=0;
while(i!=count-k){
node=node.next;
i++;
}
return node;
}
}
方法二： 快慢指針法（先讓快指針走 k-1 步，再讓快慢指針同時走）
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null || k<=0){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(k-1!=0){
fast=fast.next;
if(fast==null){
return null;
}
k--;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
5. 有序鏈表合并為一
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null && l2==null){
return null;
}
if(l1==null && l2!=null){
return l2;
}
if(l2==null && l1!=null){
return l1;
}
ListNode node=new ListNode();
ListNode head=node;
while(l1!=null && l2!=null){
while(l1!=null && l2!=null && l1.val<=l2.val){
node.next=l1;
node=node.next;
l1=l1.next;
}
while(l1!=null && l2!=null && l1.val>l2.val){
node.next=l2;
node=node.next;
l2=l2.next;
}
}
if(l1!=null){
node.next=l1;
}
if(l2!=null){
node.next=l2;
}
return head.next;
}
}
6. 編寫代碼
以給定值x為基準將鏈表分割成兩部分，所有小于x的結(jié)點排在大于或等于x的結(jié)點之前
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead==null){
return null;
}
ListNode cur=pHead;
ListNode as=null;
ListNode ae=null;
ListNode bs=null;
ListNode be=null;
while(cur!=null){
if(cur.val<x){
if(bs==null){
bs=cur;
be=bs;
}else{
be.next=cur;
be=be.next;
}
}else{
if(as==null){
as=cur;
ae=as;
}else{
ae.next=cur;
ae=ae.next;
}
}
cur=cur.next;
}
if(bs==null){
return as;
}
be.next=as;
if(as!=null){
ae.next=null;
}
return bs;
}
}
其中 bs、be、as、ae，分別為小于 x 和大于 x 的兩端的頭尾節(jié)點
7. 刪除該鏈表中重復的結(jié)點
在一個排序的鏈表中，存在重復的結(jié)點，請刪除該鏈表中重復的結(jié)點，重復的結(jié)點不保留，返回鏈表頭指針
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null){
return null;
}
ListNode node=new ListNode(0);
ListNode newHead=node;
ListNode cur=pHead;
while(cur!=null){
if(cur.next!=null && cur.val==cur.next.val){
while(cur.next!=null && cur.val==cur.next.val){
cur=cur.next;
}
cur=cur.next;
}else{
newHead.next=cur;
newHead=newHead.next;
cur=cur.next;
}
}
newHead.next=null;
return node.next;
}
}
8. 鏈表的回文結(jié)構(gòu)
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
if(A==null){
return true;
}
if(A.next==null){
return true;
}
ListNode left=A;
ListNode mid=A;
ListNode right=A;
while(right!=null && right.next!=null){
right=right.next.next;
mid=mid.next;
}
ListNode cur=mid.next;
while(cur!=null){
ListNode curNext=cur.next;
cur.next=mid;
mid=cur;
cur=curNext;
}
while(mid!=left){
if(mid.val!=left.val){
return false;
}
if(left.next==mid){
return true;
}
mid=mid.next;
left=left.next;
}
return true;
}
}
方法：
- 找中間節(jié)點
- 反轉(zhuǎn)中間節(jié)點之后的鏈表
- 將反轉(zhuǎn)鏈表頭尾進行比較
9. 輸入兩個鏈表，找出它們的第一個公共結(jié)點
public class Solution {
public int getLength(ListNode head){
if(head==null){
return 0;
}
int count=0;
while(head!=null){
count++;
head=head.next;
}
return count;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null || headB==null){
return null;
}
ListNode cur1=headA;
ListNode cur2=headB;
int length1=getLength(headA);
int length2=getLength(headB);
int i=0;
if(length1>=length2){
while(i!=length1-length2){
cur1=cur1.next;
i++;
}
}else{
while(i!=length2-length1){
cur2=cur2.next;
i++;
}
}
while(cur1!=cur2){
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}
}
方法： 因為共同節(jié)點之后，兩個鏈表的節(jié)點一樣長。只要在共同節(jié)點之前，讓兩個鏈表移動的節(jié)點與公共節(jié)點距離相等，再一步一步移動即可
10. 給定一個鏈表，判斷鏈表中是否有環(huán)
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
if(head.next==null){
return false;
}
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
方法： 快慢指針法（通過快指針追擊慢指針，能追得上則有環(huán)）
11. 給定一個鏈表
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null || head.next==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
break;
}
}
if(fast==null || fast.next==null){
return null;
}
fast=head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return fast;
}
重點： 上述題中 fast=head ，以及后面代碼含義就是找到公共節(jié)點之后，從該鏈表的頭節(jié)點，以及交點，一起一步一步移動，當兩個節(jié)點相遇時，則為第一個公共節(jié)點
分析： 上述重點不懂點可以結(jié)合下圖分析理解
- 當?shù)谝蝗妥飞蠒r： 結(jié)論為 X=Y，所以兩個節(jié)點每次移動一步就可
- 當?shù)?n 圈就追上時： 結(jié)論為 X=Y+(n-1)C。因為兩個節(jié)點移動路程是一樣的，并且交點那個節(jié)點移動 n-1 圈后，再要走 Y 正好到了起始節(jié)點。所以兩個節(jié)點每次移動一步就可
到此這篇關于數(shù)據(jù)結(jié)構(gòu)關于 Java 的鏈表詳情的文章就介紹到這了,更多相關數(shù)據(jù)結(jié)構(gòu)關于 Java 的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了springboot如何關掉tomcat容器，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
從Mybatis Plus 3.4.0版本開始，不再使用舊版本的PaginationInterceptor ，而是使用MybatisPlusInterceptor。本文就詳細的介紹一下兩者的區(qū)別，感興趣的可以了解一下2021-11-11
logback?OutputStreamAppender高效日志輸出源碼解析
這篇文章主要介紹了為大家logback?OutputStreamAppender日志輸出效率提升示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
這篇文章主要介紹了java后端如何獲取完整url的代碼問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
遇到了一個比較典型的線上問題,剛好和線程池有關,另外涉及到死鎖、jstack命令的使用、JDK不同線程池的適合場景等知識點,同時整個調(diào)查思路可以借鑒,特此記錄和分享一下2024-01-01
這篇文章主要介紹了SpringBoot 請求參數(shù)忽略大小寫的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-01-01
關于Springboot打成JAR包后讀取外部配置文件的問題
這篇文章主要介紹了關于Springboot打成JAR包后讀取外部配置文件的問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
Spring boot啟動流程之解決循環(huán)依賴的方法
循環(huán)依賴,指的是兩個bean之間相互依賴,形成了一個循環(huán),spring解決循環(huán)依賴的方式是在bean的實例化完成之后,所以不要在構(gòu)造方法中引入循環(huán)依賴,因為這時對象還沒有實例化,spring也無法解決,本文給大家介紹Spring boot循環(huán)依賴的解決方法,一起看看吧2024-02-02
本文主要介紹了maven添加jar包到本地倉庫的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-06-06
Java里的循環(huán)結(jié)構(gòu)我們可以通過while、do-while、for、foreach等方式實現(xiàn)循環(huán)，這篇文章會把這幾種循環(huán)方式都給大家講解到，但本文主要介紹for循環(huán)的使用，感興趣的同學可以參考閱讀2023-05-05