孤獨的時候看世界更清晰
?前言
數(shù)據(jù)結構的邏輯性是非常強的，所以單單看代碼很難搞懂，這里博主對每一道題目都進行了非常細致的圖文詳解，每一道題目都是非常經(jīng)典的面試OJ題，每一道題我都附上了對應的力扣鏈接，本文主要是較為簡單的題目，比較難的題目將會在下一篇博客中為大家講解，希望對大家有所幫助，謝謝！！
目錄
1. 移除鏈表元素
?1）總代碼
2. 反轉鏈表
?2）總代碼
3.?鏈表的中間結點
3）總代碼?
4. 鏈表中倒數(shù)第k個結點
4）總代碼???
?5.?合并兩個有序鏈表?
?5）總代碼
1. 移除鏈表元素
題目：刪除鏈表中等于給定值 val 的所有節(jié)點?
假設我們要刪除val=45的節(jié)點，那么我們首先要定義一個prev和cur，讓prev指向第一個節(jié)點，cur指向第二個節(jié)點，然后我們判斷cur的val是不是45？如果等于那么
prev.next = cur.next;
這樣便完成了該節(jié)點的刪除，該節(jié)點就會被回收?
?
接著我們便讓cur往后面走一步，但是prev不能動，原因是為了防止下個節(jié)點依舊是45，當下個節(jié)點不是我們要刪除的數(shù)時，就讓prev向前走，使cur和prev處于同一位置（如下圖1），然后再讓cur往后走（如下圖2）
所以我們這里要分兩種情況，一種是下個節(jié)點是我們要刪除的數(shù)，另一種是下個節(jié)點不是我們要刪除的數(shù)
while( ) { if(cur.val == val) { prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; }?當我們走到0x36這個節(jié)點，發(fā)現(xiàn)是45，滿足我們上述代碼的if條件?
?走到這里我們自然而然知道了while()的條件，那就是 cur != null ,為什么呢？當走到這一步時候，cur所處的節(jié)點56不等于45，所以執(zhí)行else里面的代碼
這樣便把所有的45刪掉了，這個時候我們return head即可，但是我們沒有考慮到頭節(jié)點是不是45的問題，所以我們還要完善，我先把上述過程進行代碼實現(xiàn)：
public ListNode removeElements(ListNode head, int val) {
ListNode prev = head; //prey表示當前可能要刪除的節(jié)點的前驅
ListNode cur = head.next; //cur表示當前可能要刪除的節(jié)點
while(cur != null) {
if(cur.val == val) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//除了頭節(jié)點，其他都刪除完成了
}到了這一步，除了頭節(jié)點我們都刪除完了，對于頭節(jié)點的處理，其實很簡單：
if(head.val == val) { head = head.next; }但是如果我們要在代碼開始就先把頭節(jié)點處理掉，這種情況的話需要加個循環(huán)，防止第一第二個節(jié)點都是我們要刪除的
?1）總代碼
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) {
return null;
}
ListNode prev = head; //prey表示當前可能要刪除的節(jié)點的前驅
ListNode cur = head.next; //cur表示當前可能要刪除的節(jié)點
while(cur != null) {
if(cur.val == val) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
//除了頭節(jié)點，其他都刪除了
if(head.val == val) {
head = head.next;
}
}
return head;
}
}2. 反轉鏈表
題目：反轉一個單鏈表?
?這道題要我們做的，其實就是頭變尾，尾變頭，最終實現(xiàn)下圖的效果
總思路：將頭節(jié)點置為空 ，然后對后續(xù)的節(jié)點都進行頭插，因為頭插法本身就可以將鏈表翻轉
具體解決操作：定義cur指向當前需要翻轉的節(jié)點
?在這里我們可以順帶處理 空表 以及 表里只有一個節(jié)點 的情況
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {return head;}
if(head.next == null) {return head;}
ListNode cur = head.next;
head.next = null;
}
}這時候 頭節(jié)點 為空，我們對 cur 進行頭插法，注意：在頭插前要先記錄一下 cur.next 不然后續(xù)的節(jié)點會丟失，即：
ListNode curNext = cur.next;? //記錄cur.next
cur.next = head;? //頭插
?頭插完后，新的頭節(jié)點就要變成cur所指的節(jié)點，即：?head = cur;
然后新的cur應該等于curNext 即：?cur = curNext;
這樣便完成了一次反轉，我們接著套上循環(huán)就可以完成整個鏈表的反轉。上述的代碼實現(xiàn)：
while(cur != null) {
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
?2）總代碼
class Solution { public ListNode reverseList(ListNode head) { if(head == null) {return head;} if(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; } }
3.?鏈表的中間結點
題目：給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。
?第一種方法：鏈表長度÷2 即可拿到中間節(jié)點，但是這種解法不是非常好
接下來博主講解第二種方法：
先定義一個 fast 和 slow
然后讓 fast? 一次走兩步， slow 一次走一步
當 fast 走向空的時候，slow 就是中間位置
原理：有長度為n的線段，A和B在同一個起點，A的速度為B的速度的兩倍，當A走到終點時，B剛好走到 n/2 處
?
上面這是個奇數(shù)的情況，在偶數(shù)條件上一樣適用?
奇數(shù)與偶數(shù)情況唯一不一樣的地方就是當代碼走到最后時：
奇數(shù)情況下:? ?fast.next = null;?
偶數(shù)情況下：fast = null;
3）總代碼?
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}4. 鏈表中倒數(shù)第k個結點
題目：輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點。?
思路：定義一個 cur 在頭節(jié)點位置，假如我們要找倒數(shù)第3個節(jié)點，那么就讓cur走 length - 3 步即可到達目標位置，假如我們要找倒數(shù)第2個節(jié)點，那么就讓cur走 length - 2 步即可
?這種解法可以解決這個問題，但需要求鏈表的長度，這里博主想跟大家分享另一個方法：
我們首先要關注到一個問題，這個K的取值范圍，如果長度為5，這里的 K <= 5? ,? K > 0
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(k <= 0 || k > size()) { return null; } } }這里把K值不合法的情況先處理掉了，可能會有人說這樣也會求鏈表的長度啊，先別急，這里只是為了便于理解，暫時這么寫，后續(xù)會刪掉的
?
思路：跟上題一樣，先定義一個 fast 和 slow ,假設我們要找倒數(shù)第二個節(jié)點，也就是說 K=2 ，我們先讓fast 走 K - 1 步，如下圖：
走完一步后，slow 和 fast 同時走，當 fast 走到 null 時候，slow就是我們要找的節(jié)點
這會不會是巧合呢？我們再來看，假設我們要找倒數(shù)第三個節(jié)點，也就是說 K = 3 ，根據(jù)上述思路讓 fast 走K-1步，所以fast會先來到如下圖所示位置：
然后讓 fast 和 slow 同時走，當 fast 走到 null 時，slow就是我們要找的節(jié)點，如下圖：
這樣是不是就能解決問題了，原理是什么呢？
我們回過頭來看，我們找倒數(shù)第二個節(jié)點的時候，是不是從后往前走一步即可，我們找倒數(shù)第三個節(jié)點的時候，是不是從后往前走兩步，依此類推，找倒數(shù)第四個節(jié)點時候，從后往前走三步，那么當我們要找倒數(shù)第K個節(jié)點時候，是不是就是從后往前走了 K - 1 步? 而我們的 fast 最后一定會到達null這個最后的位置，相當于一條線段的終點，而我們的 slow 最終會到達我們要找的位置 K ，相當于一條線段的起點，我們回過頭看上文給的思路，在一開始的時候，我們的head 和 slow 都在開始位置，如下圖一
?我們先讓fast先走 K-1 步，為什么？注意這個 K - 1，他是不是 slow 與 fast 之間的距離？也就是slow 和 fast 組成的線段的長度，
然后讓slow 和 fast 同時走，是不是就相當于把這條線段往后挪？當fast這個線段的終點到達null的時候，slow這個線段的起點就剛好落在了K位置上，這整個過程類似于我們提前測量好了窗戶的大小來制作玻璃（先讓fast先走 K-1 步），然后把玻璃挪到窗戶那里（讓slow 和 fast 同時走），就可以剛剛好安上一樣（剛好落在了K位置上），
過程如下圖：這里以k = 2 為例子。
1.讓fast走 k -1 步
?2.?讓slow 和 fast 同時走
?當fast走到null的時候就停止，這個時候slow所處位置就是我們要找的K.
代碼實現(xiàn)如下：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || k > size()) {
return null;
}
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count != k-1) {
fast = fast.next;
count++;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}我們前面說了k > size() 這個條件只是為了便于理解先這樣寫的，后續(xù)是會刪掉的，我們現(xiàn)在處理這個條件，我們設置這個條件的目的是為了什么？其實就是怕K的值太大，超過我們的表長，但是我們這個方法是不是在一開始就預先算好了k值？（fast 先走 k-1 步）如果k值太大，fast還沒有走到 k-1 步的時候就已經(jīng)超過表長了，也就是說? fast.next == null;? 所以我們可以在（fast 先走 k-1 步）這段代碼處添加一個if()else()語句，如果? fast.next ！= null;?那就讓fast繼續(xù)走 k-1 步，否則返回null。
4）總代碼???
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0) {
return null;
}
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count != k-1) {
if(fast.next != null) {
fast = fast.next;
count++;
}else {
return null;
}
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}?5.?合并兩個有序鏈表?
?題目：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的
我們以下圖兩個鏈表為例。將兩個鏈表合成一個，那么我們在結構上就要改變他，要注意這是有序鏈表，所以是升序的。那么頭節(jié)點就應該變成headB所在的那個節(jié)點。
?
?
思路：首先，我們要申請一個虛擬節(jié)點(有些書上叫 傀儡節(jié)點)，這個節(jié)點可能會有一個val值，但是這個值沒有意義：
?
?接著，我們就看兩個鏈表各個節(jié)點的val值，哪個值小就往這個虛擬節(jié)點后面串：
?
串完之后，headB往后走：
?
再比較 12 和 15 誰小，是不是12小，那么我們就把0x87那個節(jié)點的next域改成值為12的節(jié)點(0x112)，注意讓headA往后面走，然后再比較 15 和 23 誰小，誰小就串到后面，這就是這題的思路
重復上面的過程，當我們發(fā)現(xiàn)有一個鏈表已經(jīng)走到null，那么我們就不需要再比較了，因為這是個有序鏈表，我們直接把剩下的另一個鏈表直接全部串到后面即可，如下兩圖：
??
因為鏈表本身不帶頭節(jié)點的，我們實際返回的是0x87，也就是值為6的這個節(jié)點，那么如何返回呢？其實很簡單：
return newHead.next;?虛擬節(jié)點在這里起到標記作用
?思路總結：
1.創(chuàng)建虛擬節(jié)點
ListNode newHead = new ListNode(-1);?2.比較兩個鏈表的數(shù)?
這有個地方要注意?。?/strong>我們能直接動虛擬節(jié)點的next域去指向值較小的那個節(jié)點嗎？我們整個過程是不斷的去串較小值的節(jié)點，這個過程會反復用到 newHead.next = xx；? 如果直接改變虛擬頭節(jié)點的next域，那么我們最后返回的時候會無法找到頭節(jié)點，所以我們定義一個臨時變量tmp，讓tmp去走
ListNode tmp = newHead;
while(headA != null && headB != null){
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}3. 當有一個鏈表為空的時候，如下圖所示：?
if(headA != null) { //headB為空時
tmp.next = headA;
}
if(headB != null) { //headA為空時
tmp.next = headB;
}?4. 最后返回頭節(jié)點
return newHead.next;
?5）總代碼
public class Solution {
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);//創(chuàng)建虛擬節(jié)點
ListNode tmp = newHead;
while(headA != null && headB != null){
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}
}
下一篇文章博主將會講解力扣oj鏈表較難的題目，感興趣的小伙伴可以去看看文章來源：http://www.zghlxwxcb.cn/news/detail-765352.html
希望對大家有所幫助，感謝觀看！??！?文章來源地址http://www.zghlxwxcb.cn/news/detail-765352.html
到了這里，關于力扣鏈表OJ面試題，那些你不懂的全新版本解法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
