文章目錄

• 前言
• 一 刪除鏈表中等于給定值“val”的所有節點
• 二 反轉一個單鏈表
• 三 求中間節點
• 四 鏈表倒數第K個節點
• 五 合并有序鏈表
• 六 鏈表分割
• • 注意細節：
• 七 刪除重復結點
• 八 鏈表的回文結構
• 九 相交鏈表
• 十 判斷表中是否有環
• 十一 環形鏈表II
• OJ題目網址

前言

本篇文章主要就是講述數據結構中鏈表有關的一些經典的OJ題，文末也給大家提供了OJ題的具體網址供大家練習，通過這些OJ題希望對你理解鏈表有一個更深層次的理解，最后創作不易，希望大家能夠給予鼓勵，點點贊，評論交流學習！

一 刪除鏈表中等于給定值“val”的所有節點

例如：
輸入：head = [1,2,6,3,6], val = 6
輸出：[1,2,3]

圖解過程：

刪除之后

思路有了之后，代碼如下：

public nodelist deletion(int val){if (head==null)return null;nodelist cur=head;while (cur!=null){while(cur.next!=null&&cur.next.val==val){cur.next=cur.next.next;}cur=cur.next;}if(head.val==val){head=head.next;}return head;}

二 反轉一個單鏈表

例如：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

代碼具體實現

public nodelist fanzhuang(){nodelist prve=null;nodelist cur=head.next;while (cur!=null){head.next=prve;prve=head;head=cur;cur=cur.next;}head.next=prve;return head;}

三 求中間節點

給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。
例如：
head=[1,2,3,4,5] 返回3
head=[1,2,3,4] 返回3

圖解分析

代碼實現：

//中間節點問題//解決方法快慢指針public nodelist midnode(){nodelist fast=head;nodelist slow=head;while (fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}

對于兩個節點的分析方法可以自己畫圖體會，就能更好的理解這個題目。在這里我們提出一個變式，如果有兩個節點，我們要求要返回第一個節點該怎么做？
具體的代碼實現如下：

public nodelist midnode(){nodelist fast=head;nodelist slow=head;while (fast!=null&&fast.next!=null){fast=fast.next.next;if (fast==null){return slow;}slow=slow.next;}return slow;}

四 鏈表倒數第K個節點

具體代碼實現：

//求倒數第k個節點public nodelist node(int k){if (k<0||head==null)return null;nodelist slow=head;nodelist fast=head;while (k-1!=0){fast=fast.next;if (fast==null){//如果超出了范圍，那么fast應該是一個nullreturn null;}k--;}while (fast.next!=null){fast=fast.next;slow=slow.next;}return slow;}

五 合并有序鏈表

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

對于這種題目我們可以采用，創建一個新的節點，然后把他們都給串起來具體實現代碼如下：

//合并有序列表public static nodelist mergeTwoLists(nodelist head, nodelist head1) {nodelist newhead=new nodelist(-1);//創建一個新的節點nodelist cur=newhead;while(head!=null&&head1!=null){if(head.val<head1.val){cur.next=head;cur=head;head=head.next;}else{cur.next=head1;cur=head1;head1=head1.next;}}if(head==null){cur.next=head1;}else{cur.next=head;}return newhead.next;}

六 鏈表分割

問題描述：

現有一鏈表的頭指針 ListNode head，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

鏈表分割前：

分割之后：

在這里要注意的是，我們還得要先定義一個cur去遍歷鏈表，然后再利用這四個空結點將他們串起來。這里要值得注意的是對于一開始進入的as，ae，bs，be，我們需要分開討論。

注意細節：

1 如果x的值取的合適，對于分割的鏈表前半部分可能是沒有數據的，也就是說as=null，那么此時我們就必須返回bs（如果后半部分也為空，那就說明就是一個空鏈表）
2 判斷完上一個之后，我們必須要讓ae.next=bs，這樣才能把分割的鏈表鏈接起來
3 對于分割鏈表，我們不可能確保最后一個元素一定是在第二部分，也有可能是在第一部分，那么這個時候就會有一個問題，那就是這個鏈表沒有尾巴了，所以我們要把be.next置為null
具體代碼實現：

//鏈表的分割public static nodelist spiltist(nodelist head,int x){nodelist as=null;nodelist ae=null;nodelist bs=null;nodelist be=null;nodelist cur=head;if (head==null)return null;while (cur!=null){if (cur.val<x){//第一次進入if (as==null){as=cur;ae=cur;}else{//不是第一次進入ae.next=cur;ae=ae.next;}}else{//第一次進入if (bs==null){bs=cur;be=cur;}else{//不是第一次進入be.next=cur;be=be.next;}}cur=cur.next;}if (as==null){//判斷前半部分是否會有數據return bs;}ae.next=bs;//把前后兩個部分拼接起來if (bs!=null&&be.next!=null){//判斷be.next是否為null，不是null，手動置為nullbe.next=null;}return as;}

七 刪除重復結點

問題描述：

在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表 1->2->3->3->4->4->5 處理后為 1->2->5

刪除前：

刪除后：

通過以上兩張圖片，我們可以利用一個傀儡結點，去把那些不重復的節點給串起來，然后返回new.next就會是我們要得到的鏈表。
注意細節：
1 不能一眼認定，newhead.next就是head，這是不對的，因為如果一個鏈表為{1，1，2，3}，就可以說明這個錯誤的觀點
2 對于傀儡結點與鏈表直接的聯系，我們可以通過定義一個temp，讓temp=newhead，當cur.val!=cur.next.val的時候，讓temp.next=cur
具體代碼實現如下：

//刪除重復的結點public nodelist delet(){nodelist newhead=new nodelist(1);nodelist cur=head;nodelist temp=newhead;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{temp.next=cur;cur=cur.next;temp=temp.next;}}if(temp.next!=null){temp.next=null;}return newhead.next;}

這里要特別提一下最后的if語句，在這個代碼中，如果鏈表為{1，2，3，3，3}，如果沒有if語句那么最后重復的節點是刪不去的，根據上面代碼，我們要得到的就是當cur=null的時候，temp.next=null,所以在這里我們有必要在這里進行一個這樣的判斷。

八 鏈表的回文結構

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構
例如：1->2->2->1
返回：true

一 需要利用快慢指針找到中點

二 反轉鏈表

在反轉鏈表中，我們需要定義一個cur，讓cur.next=slow，這樣就完成了當前slow所在的下一個節點的反轉，我們還需要往下走，需要在定義一個curNext去記錄cur的下一個節點，不然后一個節點就找不到了，我們在把slow=cur，這樣就把slow往后移了一位，我們在令cur=curNext，curNext=curNext.next（這里的要注意要利用一個if語句判斷一下，curNext是否為null），結合上述，最終的目的就是反轉到最后一個節點（就是slow的位置要在最后一個節點上），那么我們反轉節點肯定不止一個，所以我們是需要一個循環的，那么這個循環的終止條件就是cur！=null
三 判斷回文結構
從反轉之后的圖片來看，如果是回文結構，那么此時我們slow與head同時往后走，那么就會有head與slow相遇。這里就要特別說一下，以上情況是針對奇數個節點展開的討論，偶數節點其實也是一樣的，只不過在判斷時，變成head.next=slow，具體的圖可以自己嘗試去畫一畫。在代碼中，我會把兩種情況的總代碼寫出來。
代碼展示

public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head==null||head.next==null)return false;//尋找中點ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}//反轉鏈表ListNode cur=slow.next;ListNode curNext=cur.next;while(cur!=null){cur.next=slow;slow=cur;cur=curNext;if(curNext!=null){curNext=curNext.next;}}//判斷回文結構while(head!=slow){if(head.val==slow.val){head=head.next;slow=slow.next;if(head.next==slow){return true;}}else{return false;}}return true;} }

九 相交鏈表

題目描述

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null 。

對于相交節點，我們同樣采用快慢指針的做法，設headA=slow，headB=fast，從圖中我們可以看出B比A長，那么我們就要定義一個整形，來表示B與A之間的長度之差，讓fast多走這個差步，之后fast與slow一起走，之后就會相遇，我們就返回相遇的節點

對于所給的鏈表，也可以是這種，那么這個時候也不要緊，我們可以利用一個if在前一個的基礎上來判斷一下，如果B更長，我們就可以交換一下fast與slow的指向
具體實現代碼如下：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode slow=headA;ListNode fast=headB;int lena = 0;int lenb = 0;while(slow!=null){lena++;slow=slow.next;}while(fast!=null){lenb++;fast=fast.next;}slow=headA;fast=headB;int c=lenb-lena;if(c<0){fast=headA;slow=headB;c=lena-lenb;}while(c!=0){fast=fast.next;c--;}while(fast!=slow){fast=fast.next;slow=slow.next;}return slow;} }

十 判斷表中是否有環

對于是否成環問題，我們采用快慢指針前去解決，我們讓fast一次走兩步，slow一次走一步，那么slow與fast終究會相遇的，可不敢讓fast走三次，如果只有兩個節點，那么是永遠不會相遇的
具體代碼實現如下

public class Solution {public boolean hasCycle(ListNode head) {if(head==null||head.next==null)return false;ListNode fast=head.next;ListNode slow=head;while(fast!=null&&fast.next!=null){if(fast==slow){return true;}slow=slow.next;fast=fast.next.next;}return false;} }

十一 環形鏈表II

給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

如圖我們就是要返回2這個節點，對于這種題，我們也是利用快慢指針前去解決
1 先找到fast與slow的相遇點
2 令fast與slow其中一個置為頭結點的位置，兩個一起走，就會走到入環的第一個節點
代碼實現：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow=head;ListNode fast=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;}slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}return fast;} }

OJ題目網址

1 刪除鏈表中等于給定值 val 的所有節點
2 反轉一個單鏈表
3 給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。
4 輸入一個鏈表，輸出該鏈表中倒數第k個結點。
5 將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
6 編寫代碼，以給定值x為基準將鏈表分割成兩部分，所有小于x的結點排在大于或等于x的結點之前
7 在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。
8 鏈表的回文結構
9 輸入兩個鏈表，找出它們的第一個公共結點。
10 給定一個鏈表，判斷鏈表中是否有環
11 給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null

總結

以上是生活随笔為你收集整理的详解单链表经典OJ题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。