Java鏈表面試題有哪些

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

第一題

題目：反轉一個單鏈表

每個節點是不變的，只是修改當前每個節點的指向

看圖分析：

問題分析：

每個節點是不變的，只需要修改當前每個節點的指向，第一個節點指向變成null，第二個節點的指向是第一個節點。

問題講解：

我們需要定義四個節點變量

head變量等于頭節點

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

這四步讓它是一個循環，我們再走一個循環給大家看

第五步： curNext = cur.next

第六步： cur.next = prev

第七步： prev = cur

第八步： cur = curNext

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

代碼實現：

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/

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

第二題

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

畫圖分析：

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

問題講解：

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

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

如圖：

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

代碼實現：

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/

第三題

題目：輸入一個鏈表，輸出該鏈表中倒數第k個結點

畫圖分析：

問題講解：

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

fast，slow兩個引用變量都指向頭節點

如圖： 

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

代碼實現：

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;
        
    }
}

鏈表中倒數第k個結點_牛客題霸_牛客網【牛客題霸】收集各企業高頻校招筆面試題目，配有官方題解，在線進行百度阿里騰訊網易等互聯網名企筆試面試模擬考試練習,和牛人一起討論經典試題,全面提升你的技術能力

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

第四題

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

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

 問題講解：

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

定義一個虛擬節點，假設叫newHead，在定義一個引用變量tmp等于newHead

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

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

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

 這樣就構成了我們的一個循環，當headA和headB都不為null的時候我們才能繼續循環，當循環結束，要么headA為null，要么headB為null，當headA為null，我們讓tmp.next = headB,當headB為null，我們讓tmp.next = headA,

代碼實現：

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鏈表面試題有哪些”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！