Java?鏈表實(shí)戰(zhàn)真題訓(xùn)練
每個(gè)題目后面有放對應(yīng)題目的OJ鏈接，大家可以先了解一下解題思路，然后自己先去做一下。
1、刪除值為val的所有節(jié)點(diǎn)
刪除鏈表中等于給定值val的所有節(jié)點(diǎn)。【OJ鏈接】
定義兩個(gè)指針prev、cur，cur指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，prev始終指向cur的前一個(gè)結(jié)點(diǎn)（方便刪除節(jié)點(diǎn)）。通過cur指針去遍歷鏈表，和val值比較，相同就刪除這個(gè)節(jié)點(diǎn)。最后再來比較頭節(jié)點(diǎn)。
/**
* 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、反轉(zhuǎn)鏈表
反轉(zhuǎn)一個(gè)鏈表。【OJ鏈接】
在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的 指針改為指向前一個(gè)節(jié)點(diǎn)。由于節(jié)點(diǎn)沒有引用其前一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)節(jié)點(diǎn)。在更改引用之前，還需要存儲(chǔ)后一個(gè)節(jié)點(diǎn)。最后返回新的頭引用。
/**
* 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、返回鏈表中間節(jié)點(diǎn)
給定一個(gè)帶有頭節(jié)點(diǎn)的非空單鏈表，返回鏈表的中間節(jié)點(diǎn)。如果有兩個(gè)中間節(jié)點(diǎn)，則返回第二個(gè)中間節(jié)點(diǎn)。【OJ鏈接】
我們可以定義兩個(gè)快慢指針（fast、slow），都指向頭節(jié)點(diǎn)?？熘羔樏看巫邇刹?，慢指針每次走一步。鏈表有偶數(shù)個(gè)節(jié)點(diǎn)時(shí)，fast=null時(shí)slow為中間節(jié)點(diǎn)；鏈表有奇數(shù)個(gè)節(jié)點(diǎn)時(shí)，fast.next=null時(shí)slow為中間節(jié)點(diǎn)。
/**
* 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個(gè)節(jié)點(diǎn)
輸入一個(gè)鏈表，返回該鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)。【OJ鏈接】
這個(gè)題和找中間節(jié)點(diǎn)的思路相似。定義兩個(gè)指針（fast、slow）。在K合理的前提下，我們可以讓快指針先走K-1步，然后快慢指針同時(shí)向后走，當(dāng)fast到達(dá)鏈表結(jié)尾時(shí)，slow就指向倒數(shù)第K個(gè)節(jié)點(diǎn)。
/*
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;
//先讓快節(jié)點(diǎn)走k-1步
k--;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}5、合并有序鏈表
將兩個(gè)有序鏈表合并為一個(gè)有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。【OJ鏈接】
解這個(gè)題，需要定義虛假節(jié)點(diǎn)來充當(dāng)新鏈表的頭節(jié)點(diǎn)。通過兩個(gè)鏈表的頭節(jié)點(diǎn)去遍歷兩個(gè)節(jié)點(diǎn)，去比較兩個(gè)鏈表對應(yīng)節(jié)點(diǎn)的值，將值小的節(jié)點(diǎn)連接到新鏈表的后面，知道兩個(gè)鏈表遍歷完，當(dāng)其中一個(gè)鏈表為空時(shí)，直接將另一個(gè)鏈表連接到新鏈表后面即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
//創(chuàng)建虛擬節(jié)點(diǎn)，充當(dāng)新鏈表的頭節(jié)點(diǎn)，值不代表任何意義
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、按值分割鏈表
將一個(gè)鏈表按照給定值X劃分為兩部分，所有小于X的節(jié)點(diǎn)排在大于或等于X的節(jié)點(diǎn)之前。不改變節(jié)點(diǎn)原來的順序。【OJ鏈接】
首先我們需要定義四個(gè)指針（bs、be、as、ae）分別表示小于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)、大于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。通過頭節(jié)點(diǎn)遍歷鏈表，將鏈表分為兩部分。最后將兩個(gè)鏈表連接起來即可。需要特別注意，當(dāng)小于X部分鏈表不為空時(shí)，我們需要手動(dòng)將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部分即可。此時(shí)ae.next一定為null
}
be.next=as;//否則連接小于X和大于X部分
if(as!=null){
ae.next=null;
//當(dāng)小于X部分不為空時(shí)，ae.next可能不為null，需要手動(dòng)置為null
}
return bs;
}
}7、判讀回文鏈表
判斷鏈表是不是回文鏈表。【OJ鏈接】
首先我們需要找到鏈表的中間節(jié)點(diǎn)，然后將后半段鏈表反轉(zhuǎn)。最后通過兩邊來逐步比較即可。特別注意，當(dāng)鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，因?yàn)橹虚g節(jié)點(diǎn)的緣故，兩邊遍歷時(shí)，無法相遇，需要特殊處理。
/*
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;
}
//求鏈表的中間節(jié)點(diǎn)
ListNode slow=A;
ListNode fast=A;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
//反轉(zhuǎn)后半段鏈表
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、找兩個(gè)鏈表的公共節(jié)點(diǎn)
輸入兩個(gè)鏈表，輸出兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)。沒有返回NULL。【OJ鏈接】
兩個(gè)鏈表相交呈現(xiàn)Y字型。那么兩個(gè)鏈表長度的差肯定是未相交前兩個(gè)鏈表節(jié)點(diǎn)的差。我們需要求出兩個(gè)鏈表的長度。定義兩個(gè)指針（pl、ps），讓pl指向長的鏈表，ps指向短的鏈表。求出兩個(gè)鏈表的長度差len。讓pl想走len步。這樣兩個(gè)鏈表的剩余長度就相同。此時(shí)兩個(gè)指針同時(shí)遍歷連個(gè)鏈表，如果其指向一致，則兩個(gè)鏈表相交，否則，兩個(gè)鏈表不相交。
/**
* 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、判斷成環(huán)鏈表
判斷鏈表中是否有環(huán)。【OJ鏈接】
還是快慢指針。慢指針一次走一步，快指針一次走兩步。兩個(gè)指針從鏈表起始位置開始運(yùn)行。如果鏈表帶環(huán)則一定會(huì)在環(huán)中相遇，否則快指針率先走到鏈表的末尾。
【拓展】
/**
* 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;//鏈表為空或者只有一個(gè)節(jié)點(diǎn)時(shí)，沒有環(huán)
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
//如果快慢節(jié)點(diǎn)可以相遇，表示鏈表有環(huán)
}
}
return false;
}
}10、返回成環(huán)鏈表的入口
給定一個(gè)鏈表，判斷鏈表是否有環(huán)并返回入環(huán)的節(jié)點(diǎn)。如果沒有環(huán)，返回NULL。【OJ鏈接】
讓一個(gè)指針從鏈表的其實(shí)在位置開始遍歷，同時(shí)另一個(gè)指針從上題中兩只真相與的位置開始走，兩個(gè)指針再次相遇時(shí)的位置肯定為環(huán)的入口
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
//判斷鏈表是否有環(huán)，并返回第一次快慢節(jié)點(diǎn)相交的位置
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;
}
//當(dāng)返回的結(jié)點(diǎn)與頭節(jié)點(diǎn)再次相交時(shí)，為環(huán)的入口
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;
}
}到此這篇關(guān)于Java 鏈表實(shí)戰(zhàn)真題訓(xùn)練的文章就介紹到這了,更多相關(guān)Java 鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了SpringSecurity自定義登錄成功處理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-09-09
筆者前幾日在開服過程中需要將字符串轉(zhuǎn)化成為16進(jìn)制的字符串,在網(wǎng)上找到了一些方法嘗試之后,均發(fā)現(xiàn)存在一個(gè)問題-->字符串轉(zhuǎn)為16進(jìn)制后再轉(zhuǎn)回來,英文正常,中文出現(xiàn)亂碼2009-05-05
springboot實(shí)現(xiàn)對注解的切面案例
這篇文章主要介紹了springboot實(shí)現(xiàn)對注解的切面過程，首先定義一個(gè)注解、再編寫對注解的切面只是記錄的執(zhí)行時(shí)間和打印方法，可以實(shí)現(xiàn)其他邏輯,需要的朋友可以參考一下2022-01-01
這篇文章主要介紹了Ubuntu 使用Jni開發(fā)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2016-10-10
這篇文章主要介紹了Java中對象序列化與反序列化,較為詳細(xì)的分析了java中對象序列化的概念、原理、實(shí)現(xiàn)方法及相關(guān)注意事項(xiàng),具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-09-09
今天小編就為大家分享一篇java把字符串轉(zhuǎn)化成公式計(jì)算的示例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
springMVC+jersey實(shí)現(xiàn)跨服務(wù)器文件上傳
這篇文章主要介紹了springMVC+jersey實(shí)現(xiàn)跨服務(wù)器文件上傳，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-08-08
Kotlin基礎(chǔ)教程之伴生對象,getter,setter,內(nèi)部,局部,匿名類,可變參數(shù)
這篇文章主要介紹了Kotlin基礎(chǔ)教程之伴生對象,getter,setter,內(nèi)部,局部,匿名類,可變參數(shù)的相關(guān)資料,需要的朋友可以參考下2017-05-05
Java OpenCV實(shí)現(xiàn)圖像鏡像翻轉(zhuǎn)效果
這篇文章主要為大家詳細(xì)介紹了Java OpenCV實(shí)現(xiàn)圖像鏡像翻轉(zhuǎn)效果，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07
這篇文章主要帶你掌握J(rèn)ava中包的定義及使用以及Java中的4種訪問權(quán)限，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-09-09