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