Java鏈表面試題有哪些

這篇文章主要為大家展示了“Java鏈表面試題有哪些”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java鏈表面試題有哪些”這篇文章吧。

第一題

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

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

看圖分析：

問題分析：

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

代碼實(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/

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

第二題

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

畫圖分析：

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

問題講解：

同樣的，我們來定義兩個(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è)就是走了路程的一半。有這樣的思路我們就可以來寫代碼了 ，同樣的先要判斷一下鏈表是不是為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)

畫圖分析：

問題講解：

同樣的，我們來定義兩個(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;
        
    }
}

鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)_?？皖}霸_牛客網(wǎng)【?？皖}霸】收集各企業(yè)高頻校招筆面試題目，配有官方題解，在線進(jìn)行百度阿里騰訊網(wǎng)易等互聯(lián)網(wǎng)名企筆試面試模擬考試練習(xí),和牛人一起討論經(jīng)典試題,全面提升你的技術(shù)能力

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

第四題

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

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

 問題講解：

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

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

 首先我們先來比較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;
 
    }
}

以上是“Java鏈表面試題有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！