前言：

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

第一題

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

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

看圖分析：

問(wèn)題分析：

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

問(wèn)題講解：

我們需要定義四個(gè)節(jié)點(diǎn)變量

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

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

這四步讓它是一個(gè)循環(huán)，我們?cè)僮咭粋€(gè)循環(huán)給大家看

第五步： curNext = cur.next

第六步： cur.next = prev

第七步： prev = cur

第八步： cur = curNext

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

代碼實(shí)現(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/

題目鏈接在上面，大家一定打開(kāi)鏈接自己做一下。

第二題

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

畫(huà)圖分析：

 問(wèn)題分析：奇數(shù)的話(huà)返回中間的節(jié)點(diǎn)，偶數(shù)的話(huà)返回第二個(gè)中間節(jié)點(diǎn)，也就是說(shuō)偶數(shù)返回第三個(gè)。

問(wèn)題講解：

同樣的，我們來(lái)定義兩個(gè)引用變量

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

如圖：

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

代碼實(shí)現(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/

第三題

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

畫(huà)圖分析：

問(wèn)題講解：

同樣的，我們來(lái)定義兩個(gè)引用變量

fast，slow兩個(gè)引用變量都指向頭節(jié)點(diǎn)

如圖： 

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

代碼實(shí)現(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;
        
    }
}

題目鏈接

第四題

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

畫(huà)圖分析：這是我們的兩個(gè)鏈表 

 問(wèn)題講解：

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

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

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

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

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

 這樣就構(gòu)成了我們的一個(gè)循環(huán)，當(dāng)headA和headB都不為null的時(shí)候我們才能繼續(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,

代碼實(shí)現(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/

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

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

最新評(píng)論