前言：

上一章更到了鏈表，雖然知道了什么是鏈表，鏈表的結(jié)構(gòu)是怎么樣的，但這是遠遠不夠的，我們只清楚了點皮毛，如果讓你做題你還是會無從下手，所以我們必須多做題，在做題的過程中慢慢的我們就會覺得一切都很簡單。下面我們就來做幾道經(jīng)典的鏈表面試題?。。。。?！

第一題

題目：反轉(zhuǎn)一個單鏈表

每個節(jié)點是不變的，只是修改當(dāng)前每個節(jié)點的指向

看圖分析：

問題分析：

每個節(jié)點是不變的，只需要修改當(dāng)前每個節(jié)點的指向，第一個節(jié)點指向變成null，第二個節(jié)點的指向是第一個節(jié)點。

問題講解：

我們需要定義四個節(jié)點變量

head變量等于頭節(jié)點

cur = head

prev = null

curNext = cur.next

第一步：curNext = cur.next

第二步：cur.next = prev

第三步：prev = cur

第四步：cur = curNext

我們看一下圖解是如何走的

第一步：curNext = cur.next

第二步：cur.next = prev

第三步： prev = cur

第四步： cur = curNext

這四步讓它是一個循環(huán)，我們再走一個循環(huán)給大家看

第五步： curNext = cur.next

第六步： cur.next = prev

第七步： prev = cur

第八步： cur = curNext

這樣兩個循環(huán)下來我想大家看的就很明白了，那既然是循環(huán)肯定會有終止條件，所以我們可以看一下，當(dāng)cur走到最后一個字節(jié)的時候，我們?nèi)匀恍枰?cur.next =  prev，再往后走的話cur就為null了，為null的時候就反轉(zhuǎn)結(jié)束了。所以我們循環(huán)的終止條件就是cur != null。另外我們還需要判斷一直指向頭節(jié)點的head為不為null，如果為null的話就是沒有這個鏈表，直接返回null就可以了。反轉(zhuǎn)完成后最后一個節(jié)點就變成了頭節(jié)點，所以我們返回prev就可以了、那我們就可以來寫代碼了。

代碼實現(xiàn)：

lass Solution {
    public ListNode reverseList(ListNode head) {
         if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode prev = null;
 
        while (cur != null) {
            ListNode cutNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = cutNext;
        }
        return prev;
 
    }
}

力扣

https://leetcode-cn.com/problems/reverse-linked-list/description/

題目鏈接在上面，大家一定打開鏈接自己做一下。

第二題

題目：給定一個帶有頭結(jié)點 head 的非空單鏈表，返回鏈表的中間結(jié)點。如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。 

畫圖分析：

 問題分析：奇數(shù)的話返回中間的節(jié)點，偶數(shù)的話返回第二個中間節(jié)點，也就是說偶數(shù)返回第三個。

問題講解：

同樣的，我們來定義兩個引用變量

fast，slow兩個引用變量都等于head頭節(jié)點

如圖：

我們讓fast一次走兩步，slow一次走兩步，奇數(shù)情況：fast.next為null，slow所在的就是中間節(jié)點位置 。偶數(shù)情況：fast為null，low所在的就是中間節(jié)點位置 。原因是為什么呢？兩個同時走，fast的速度是slow的兩倍，那么路程也是兩倍，一個走到終點了，那么另一個就是走了路程的一半。有這樣的思路我們就可以來寫代碼了 ，同樣的先要判斷一下鏈表是不是為null，為null直接返回null就好了

代碼實現(xiàn)：

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null ){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }  
}

力扣

https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

第三題

題目：輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點

畫圖分析：

問題講解：

同樣的，我們來定義兩個引用變量

fast，slow兩個引用變量都指向頭節(jié)點

如圖： 

如果我們要找倒數(shù)第K個，從第K個到倒數(shù)第1個需要走K-1步，所以我們先讓fast走K-1步，當(dāng)走完K-1步，fast指向的是倒數(shù)第一個時候，那么slow就是我們要找的倒數(shù)第K給，如果fast走完K-1步，fast指向的不是倒數(shù)第一個，那么這個時候我們讓fast和slow一起往后走，他們始終差了K-1步，當(dāng)fast 走到倒數(shù)第一個的時候，這個時候slow所指向的節(jié)點就是我們要找的倒數(shù)第K個。這里K我們也要判斷一下，如果K<=0 或者 k>鏈表的長度，我們直接返回null就可以了。

代碼實現(xiàn)：

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){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            k--;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
        
    }
}

題目鏈接

第四題

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

畫圖分析：這是我們的兩個鏈表 

 問題講解：

同樣的，先定義兩個引用變量headA和headB分別指向兩個鏈表的頭節(jié)點。

定義一個虛擬節(jié)點，假設(shè)叫newHead，在定義一個引用變量tmp等于newHead

 首先我們先來比較headA和headB的大小，如果headA.val<headB.val,那么就讓tmp.next等于headA

 因為12小，那么就讓headA = headA.next，如果后面再找到比12大數(shù)字就要放在12的后頭，所以我們讓tmp = tmp.next，

這個時候再比較headA和headB, 如果headA.val>headB.val,那么就是讓tmp.next = headB，再讓headB = headB.next，tmp = tmp.next

 這樣就構(gòu)成了我們的一個循環(huán)，當(dāng)headA和headB都不為null的時候我們才能繼續(xù)循環(huán)，當(dāng)循環(huán)結(jié)束，要么headA為null，要么headB為null，當(dāng)headA為null，我們讓tmp.next = headB,當(dāng)headB為null，我們讓tmp.next = headA,

代碼實現(xiàn)：

lass Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
 ListNode newhead = new ListNode(-1);
       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 = headB;
           }
           if(headB == null){
               tmp.next = headA;
           }
       return newhead.next;
 
    }
}

 力扣

https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

因為時間原因：今天就先打卡這4道面試題，這4道面試題都是比較經(jīng)典的面試題，對我們鏈表這塊的學(xué)習(xí)會很有幫助。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)就是要多刷題，這樣你才能完全掌握數(shù)據(jù)結(jié)構(gòu)這門知識。今天太晚了，明天再繼續(xù)給大家更面試題吧。有任何疑問大家都可以私信我，有問題歡迎大家指出來，我都會虛心學(xué)習(xí)的，希望可以和大家一起進步。

到此這篇關(guān)于Java 詳細分析力扣鏈表面試題的文章就介紹到這了,更多相關(guān)Java 鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論