?博主主頁: 33的博客?
??文章專欄分類:數(shù)據(jù)結構??
??我的代碼倉庫: 33的代碼倉庫??
??????關注我?guī)銓W更多數(shù)據(jù)結構知識
1.前言
在上一篇文章中博主已經(jīng)介紹了鏈表的基礎知識，什么是鏈表，如何實現(xiàn)一個鏈表，以及LinkedList的操作方法，那么在這篇文章中通過一些鏈表的經(jīng)典習題來練習吧。
2.刪除值為key的所有結點
刪除值為val的所有結點：OJ鏈接
解題思路：
1.遍歷鏈表。
2.如果某個結點A的值等于key，那么A的前一個結點B的next值直接等于A的next。
3，繼續(xù)遍歷，遇到等于值等于key的重復上訴操作，直到全部遍歷完成。
public void removeAllKey(int key) {
if (head==null){
return;
}
Node node=head;
Node cur=head.next;
while (cur!=null){
if(cur.val==key){
node.next=cur.next;
cur=cur.next;
}else {
node=node.next;
cur=cur.next;
}
}
if(head.val==key){
head=head.next;
}
}
3.反轉鏈表
反轉鏈表：OJ鏈接
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode cur=head.next;
head.next=null;
while (cur!=null){
ListNode curNext=cur.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}
4.返回中間結點
返回中間結點：OJ鏈接
方式一：
解題思路：
1.求鏈表的大小size
2.中間結點為size/2
遍歷鏈表，走到size/2的位置，返回該節(jié)點
class Solution {
//求鏈表長度
public int size(ListNode head) {
ListNode node=head;
int count=0;
while (node!=null){
count++;
node=node.next;
}
return count;
}
public ListNode middleNode(ListNode head) {
if(head==null||head.next==null){
return head;
}
int Size=size(head);
int middle=Size/2;
ListNode node=head;
for (int i=0;i<middle;i++){
node=node.next;
}
return node;
}
}
方式二：
解題思路：
1.設置一個快結點：fast，設置一個慢結點：slow。
2.我們試想：如果fast的速度是slow的兩倍，那么當fast到達路程的終點時，此時slow就走了路程的一半。
3.所以我們讓fast每次走兩步，slow每次走一步，當fast=null或者fast.next=null的時候，slow就是中間結點
public Node middleNode2() {
Node fast=head;
Node slow=head;
while (fast!=null||fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
5.輸出倒數(shù)第k個結點
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點：OJ鏈接
解題思路：
1。讓fast先走k-1步數(shù)
2.再同時走，當fast到達終點時，那么它們就相差k
3.此時的slow就是倒數(shù)第k個結點
ublic Node FindKthToTail (int k) {
Node fast=head;
Node slow=head;
if(k<=0||head==null){
return null;
}
while (k-1>0){
fast=fast.next;
k--;
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
6.鏈表分割
以給定值x為基準將鏈表分割成兩部分，所有小于x的結點排在大于或等于x的結點之前：OJ鏈接
解題思路：
1.首先，遍歷鏈表
2.再創(chuàng)建兩個鏈表，一個用于存放小于x的值，另一個用于存放大于x的值
3.再把第一個鏈表的最后一個結點與第二個鏈表的頭節(jié)點串起來。
public Node partition(int x) {
if (head==null){
return null;
}
Node as=null;
Node ae=null;
Node bs=null;
Node be=null;
Node cur=head;
while (cur!=null){
if (cur.val<x){
if(as==null){
//插入第一個節(jié)點
as=cur;
ae=cur;
cur=cur.next;
} else {
ae.next=cur;
ae=ae.next;
cur=cur.next;
}
}else {
//cur.val>x
if(bs==null){
//插入第一個節(jié)點
bs=cur;
be=cur;
cur=cur.next;
} else {
be.next=cur;
be=be.next;
cur=cur.next;
}
}
}
//如果第一個鏈表為空就直接返回第二個鏈表的頭節(jié)點
if(as==null){
return bs;
}
ae.next=bs;
if(bs != null) {
//第2個區(qū)間有數(shù)據(jù)
be.next = null;
}
head=as;
return head;
}
7.鏈表回文
給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構：OJ鏈接
解題思路：
1.查看鏈表是否回文，是指從前向后遍歷，或者從后向前遍歷，輸出的之都相同。
2.我們可以先找到中間位置，再從中間位置進行翻轉，使它同時從兩頭向中間遍歷
3.遍歷的時候如果如果鏈表有偶數(shù)個的情況，和有奇數(shù)個的情況是不一樣的，當有奇數(shù)個時，走到相同的位置就停止，當有偶數(shù)個時，當下再走一步就相遇時就停止。
public boolean chkPalindrome() {
if(head == null || head.next == null) {
return true;
}
//按照中間位置翻轉鏈表
//1.找到中間位置（middle已經(jīng)在4中寫過）
Node middle=middleNode2();
//2.翻轉
Node ehead=middle;
Node cur=ehead.next;
while (cur!=null){
Node curNext=cur.next;
cur.next=ehead;
ehead=cur;
cur=curNext;
}
//從兩頭開始遍歷
Node snode=head;
Node enode=ehead;
while (snode!=enode){
if (snode.val!=enode.val){
return false;
}
if (snode.next==enode){
return true;
}
snode=snode.next;
enode=enode.next;
}
return true;
}
8.相交鏈表
給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點:OJ鏈接
解題思路：
1.求兩個鏈表的長度，再求長度差值
2.定義節(jié)點fast代表長的鏈表頭節(jié)點，slow代表短的鏈表的頭節(jié)點。先讓長的鏈表先走差值步，再同時走。
3.兩個鏈表相遇時就是相交節(jié)點。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode nodeA=headA;
ListNode nodeB=headB;
int lenA=size(headA);
int lenB=size(headB);
ListNode fast=headA;
ListNode slow=headB;
int len=lenA-lenB;
if(len<0){
len=lenB-lenA;
fast=headB;
slow=headA;
}
while(len>0){
fast=fast.next;
len--;
}
while(fast!=slow&&fast!=null){
fast=fast.next;
slow=slow.next;
}
return fast;
}
9.環(huán)形鏈表
9.1是否為環(huán)形鏈表
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán):OJ鏈接
解題思路：
1.定義節(jié)點fast代表長的鏈表頭節(jié)點，slow代表短的鏈表的頭節(jié)點.
2.每次讓fast走兩步，slow走一步，如果是環(huán)形鏈表，那么它們一定會在環(huán)中的某一個位置相遇，否則不是環(huán)形鏈表
為什么每次讓fast走兩步，slow走一步？不可以fast走3步，4步嗎？假設環(huán)中只有兩個元素A,B，當slow進入環(huán)時在A的節(jié)點的位置，此時fast在B節(jié)點的位置，slow走一步就到B的位置，fast走3步就到A的位置，那么它們永遠都不會相遇。
只有每次讓fast走兩步，slow走一步，換的長度為1，那么肯定會相遇。
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
//fast.next!=null&&fast!=null，不能這樣寫
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
9.2入環(huán)第一個節(jié)點
給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null:OJ鏈接
解題思路：
讓一個指針從鏈表起始位置開始遍歷鏈表，同時讓一個指針從判環(huán)時相遇點的位置開始繞環(huán)運行，兩個指針都是每次均走一步，最終肯定會在入口點的位置相遇。
證明如下：
public class Solution {
ListNode hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
//fast.next!=null&&fast!=null，不能這樣寫
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return fast;
}
}
return null;
}
public ListNode detectCycle(ListNode head) {
ListNode fast=hasCycle(head);
if(fast==null){
return null;
}
ListNode slow=head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return fast;
}
}
10.總結
本篇博客主要對鏈表的經(jīng)典習題進行了講解，同學們要理解解題的一些思想做到融會貫通，如果有疑惑的地方歡迎大家來和博主溝通，交流。文章來源：http://www.zghlxwxcb.cn/news/detail-855233.html
下期預告：棧文章來源地址http://www.zghlxwxcb.cn/news/detail-855233.html
到了這里，關于【數(shù)據(jù)結構（四）】鏈表經(jīng)典練習題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
