鏈表面試題:

第一題 : 移除鏈表元素

解題思路:

畫圖決議:

具體代碼:

第二題 : 反轉鏈表

解題思路:

畫圖決議:

具體代碼:

第三題 : 鏈表的中間結點

解題思路:

畫圖決議:

具體代碼:

第四題 : 鏈表中倒數第k個結點

解題思路:

畫圖決議:

? 具體代碼:

第五題 : 合并兩個有序鏈表

解題思路:

畫圖決議:

?具體代碼:

第六題 : 鏈表分割

解題思路:

畫圖決議:

? 具體代碼:

第七題 : 洗掉鏈表中重復的結點

解題思路:

畫圖決議:

?代碼實作:

第八題 : 鏈表的回文結構

解題思路:

畫圖決議:

代碼實作:

第九題 : 相交鏈表

解題思路:

畫圖決議:

代碼實作:

第十題 : 環形鏈表

解題思路:

畫圖決議:

代碼實作:

十一題 : 環形鏈表 II

解題思路:

畫圖決議:

代碼實作:

鏈表面試題:

第一題 : 移除鏈表元素

Leetcode 203:

給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，

解題思路:

1.首先判斷鏈表是否為空,為空直接回傳null即可

2.用cur參考指向head,curNext指向head.next,此時cur就是前驅節點,讓curNext去找要洗掉的節點,如果curNext.val是要洗掉的節點的,那么讓cur.next=curNext.next,如果curNext.val不是要洗掉的節點,cur=curNext.這里可以運用一個回圈,回圈條件就是curNext != null.

3.最后判斷當頭節點為要洗掉的情況,直接讓head=head.next,如果只有head一個節點,head就指向null.

畫圖決議:

具體代碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode cur = head;
        ListNode curNext = head.next;
        while(curNext !=null ) {
            if (curNext.val == val){
                cur.next = curNext.next;
            }else {
                cur.next = curNext;
                cur = curNext;
            }
                curNext = curNext.next;
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

第二題 : 反轉鏈表

Leetcode206:

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

示例 1：

解題思路:

1.首先判斷單鏈表是否為空,為空直接回傳null.

2.判斷head.next是否為空,為空直接回傳head.

3.先讓cur參考指向head.next,讓prev參考指向head,回圈,如果cur=null時,回圈結束.在回圈中參考一個curNext=cur.next,然后讓cur節點的地址指向prev節點的地址即,cur.next=prev;再讓prev指向cur節點,即prev=cur,然后讓cur指向下一個節點,cur=curNext(因為cur.next已經改變,所以讓curNext表示下一個節點的地址);

4.執行回圈后,head節點指向的地址還沒有改變,所以讓head節點指向的地址為null,即head.next=null,再換頭,即讓頭節點指向prev節點,head=prev;

畫圖決議:

具體代碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null) {
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur!=null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        head.next = null;
        head = prev;
        return head;
    }
}

第三題 : 鏈表的中間結點

Leetcode 876:

給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，

如果有兩個中間結點，則回傳第二個中間結點，

示例 1：

輸入：[1,2,3,4,5]
輸出：此串列中的結點 3 (序列化形式：[3,4,5])
回傳的結點值為 3 ， (測評系統對該結點序列化表述是 [3,4,5])，
注意，我們回傳了一個 ListNode 型別的物件 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

解題思路:

1.判斷單鏈表是否為空,為慷訓傳null

2.這題是求中間節點的,相當于求的是中間值,這時可以定義一個參考fast,和slow,讓fast走兩步,slow走一步.此時fast的速度是slow的兩倍,時間不變,路程等于速度乘時間,路程也是兩倍,相當于fast走到結尾的時候,slow就正好在中間位置.

3.fast走兩步 fast=fast.next.next; slow走一步 slow=slow.next;

4.此時分為兩種情況,一種為單數,一種為雙數.單數的情況下,fast走到末尾,fast.next為空,雙數時,fast走到末尾時,fast為空,所以此時要判斷兩種情況是否為空,為慷訓圈結束

畫圖決議:

具體代碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}

第四題 : 鏈表中倒數第k個結點

描述

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

示例1

輸入：

1,{1,2,3,4,5}

回傳值：

{5}

解題思路:

1.首先判斷鏈表是否為空,如果是空直接回傳null

2.可以根據k的不同值可以判斷出,k距離最后一個位置的距離為k-1

3.讓fast先走k-1,slow不動,此時slow與fast的距離就是k與最后一個位置的距離,然后再讓fast繼續走,當fast為空的時候停止,此時slow所指向的位置就是倒數第k個節點的位置;

4.還要判斷k所給值的合法性,當k小于0的時候不合法,當k＞鏈表長度不合法,如果要求鏈表長度就太麻煩了,可以在讓fast先走k-1步的時候判斷,fast.next是否為空為空就return null,就解決了求鏈表長度的問題.

畫圖決議:

具體代碼:

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        if(k<0){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while( k-1 != 0){
            if(fast.next==null){
                return null;
            }
            fast = fast.next;
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

第五題 : 合并兩個有序鏈表

將兩個升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例 1：

解題思路:

1.這題可以引用一個傀儡節點newHead,讓newHead的值為-1,指向的地址為null;

2.讓headA.val與headB.val進行比較

如果headA.val<headB.val 就讓cur.next指向headA的地址,讓headA指向下一個節點,cur就指向cur.next;

如果headA.val>=headB.val,就讓cur.next指向headB的地址,讓headB指向下一個節點,cur就指向cur.next;

3.回圈此步驟,當headA為慷訓者headB為空的時候,結束回圈

4.如果回圈結束還有節點沒連上,所以就讓cur.next連上剩余的節點,判斷是哪個head為空時,回圈結束.此時看題目A末尾的資料在B之前,所以讓判斷headA的陳述句放在前面,因此也解決了鏈表為空的情況.

畫圖決議:

具體代碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while(headA != null && headB !=null) {
            if(headA.val < headB.val){
                cur.next = headA;
                headA = headA.next;
                cur = cur.next;
            }else{
                cur.next = headB;
                headB = headB.next;
                cur = cur.next;
            }
        }
        if(headA != null){
            cur.next = headA;
        }
        if(headB != null){
            cur.next = headB;
        }
        return newHead.next;
    }
}

第六題 : 鏈表分割

描述

現有一鏈表的頭指標 ListNode* pHead，給一定值x，撰寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的資料順序，回傳重新排列后的鏈表的頭指標，

解題思路:

1.可以用兩個鏈表分別來表示,小于x的和大于x的,再將2個鏈表連起來即可.

2. 兩個鏈表分別用bs表示第一個鏈表的頭,be表示第一個鏈表的尾,as表示第二個鏈表的頭,ae表示第二個鏈表的尾.

3.參考一個cur指向head,比較cur.val與x的值,如果小于x的時候,bs,be就指向cur,如果大于x的時候,as,ae就指向cur.這一步只執行一次,可以通過判斷bs是否為空,as是否為空來解決.

4.第一次的執行之后,就進入else,如果小于x的時候,be.next=cur,be=be.next;如果大于x的時候,ae.next=cur,ae=ae.next;

5.然后要連接2個鏈表;

有3種情況

①bs為空,回傳as

②bs不為空,連接be,as,即be.next=as.next;

③當ae不為空,ae指向的地址可能不為空,所以要ae.next=null;

畫圖決議:

具體代碼:

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode head, int x) {
        // write code here
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }
            else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs==null){
               return as;
        }
            be.next = as;
        if(as!=null){
            ae.next = null;
        }
        return bs;
    }
}

第七題 : 洗掉鏈表中重復的結點

描述

在一個排序的鏈表中，存在重復的結點，請洗掉該鏈表中重復的結點，重復的結點不保留，回傳鏈表頭指標，例如，鏈表 1->2->3->3->4->4->5 處理后為 1->2->5

例如輸入{1,2,3,3,4,4,5}時，對應的輸出為{1,2,5}，對應的輸入輸出鏈表如下圖所示：

解題思路:

1.參考一個傀儡節點當作頭,把去重后的節點連接到傀儡節點上;

2.參考一個tmp指向傀儡節點,參考一個cur指向head;

3.當cur.val == cur.next.val的時候,要讓cur=cur.next;當跳過這個節點之后,cur.val還是需要刪掉的資料,所以要再cur=cur.next一次才能指向下一個節點,

4.重復的數可能有2個3個或者多個,可以用回圈來解決

5.當cur.val != cur.next.val的時候,讓tmp指向cur的地址,tmp就到tmp.next節點上,cur就移到下一個節點.

6.由代碼看出來,在判斷cur.next.val的時候,cur.next可能為空,所以要在判斷時,加上cur.next != null

7.最后tmp節點所指向的地址可能不為空,所以在最后要讓tmp.next=null;

畫圖決議:

代碼實作:

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = head;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next !=null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                    cur = cur.next;
            }else{
                tmp.next = cur;
                tmp=tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }
}

第八題 : 鏈表的回文結構

描述

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的演算法，判斷其是否為回文結構，

給定一個鏈表的頭指標A，請回傳一個bool值，代表其是否為回文結構，保證鏈表長度小于等于900，

解題思路:

1.判斷鏈表是否為空

2.找中間節點定義兩個參考fast和slow,一個走兩步,一個走一步

3.反轉,定義一個參考cur等于slow的下一個節點的地址,然后讓cur的下一個節點地址等于slow的地址,再讓slow等于cur的節點,這時cur.next被修改了,所以在前面要定義一個curNext記錄cur.next的地址,最后讓cur=curNext.回圈直到,cur=null結束

4.判斷回文

①奇數 head=slow

②偶數 head.next=slow

畫圖決議:

代碼實作:

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        //鏈表為空
        if(head == null) {
            return true;
        }
        //1.找中間節點
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.反轉
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //判斷回文
        while(head != slow){
            //偶數情況
            if(head.next==slow){
                return true;
            }
            if(head.val != slow.val){
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

第九題 : 相交鏈表

Leetcode 160:

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表沒有交點，回傳 null ，

圖示兩個鏈表在節點 c1 開始相交：

題目資料保證整個鏈式結構中不存在環，

注意，函式回傳結果后，鏈表必須保持其原始結構，

解題思路:

1.首先分析兩個鏈表相交的形狀,只能為Y形狀

2.再分析相交時,是val域相同還是next域相同

3.因為要保持原始結構,所以要定義兩個參考pl,ps

4.pl始終指向最長的鏈表,ps始終指向最短的鏈表

5.先讓pl指向headA,ps指向headB,求headA和headB鏈表的長度,lenA和lenB

6.求差值len=lenA-lenB,如果len<0的時候,讓pl指向headB,ps指向headA,

7.如果len>=0的時候,pl和ps已經走到最后,所以要讓他們重新指向開頭

8.然后讓pl走差值步,這樣在同時走的時候next域才會相等時

8.最后讓回圈判斷pl是否等于ps,相等時,回傳pl即可

9.最開始判斷鏈表是否為空,為慷訓傳null;

畫圖決議:

代碼實作:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         if(headA == null || headB == null) {
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;

        int lenA = 0;
        int lenB = 0;

        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }

        int len = lenA - lenB;//差值步
        //len小于0的時候要讓pl指向最長的,ps指向最短的
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }else{
            //讓pl和ps重新指向頭節點
            pl = headA;
            ps = headB;
        }
        //讓pl走差值步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }
}

第十題 : 環形鏈表

Leetcode 141:

給定一個鏈表，判斷鏈表中是否有環，

如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環，為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始），如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，

如果鏈表中存在環，則回傳 true ，否則，回傳 false ，

進階：你能用 O(1)（即，常量）記憶體解決此問題嗎？

解題思路:

1.先判斷鏈表是否為空,為慷訓傳null

2.定義兩個參考,一個快一個慢,讓fast走兩步,slow走一步,這樣總會相遇.

3.相遇了fast=slow的時候,就是換裝鏈表

畫圖決議:

代碼實作:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

十一題 : 環形鏈表 II

給定一個鏈表，回傳鏈表開始入環的第一個節點，如果鏈表無環，則回傳 null，

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始），如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用于標識環的情況，并不會作為引數傳遞到函式中，

說明：不允許修改給定的鏈表，

進階：你是否可以使用 O(1) 空間解決此題？

示例 1：

解題思路:

1.判斷鏈表是否為空,為空直接回傳null

2.定義兩個參考fast和slow,fast速度是slow的兩倍,他們相遇時,就是相遇點

3.設起始點為A,入口點為B,相遇點為C.設起始點到入口點的距離A->B為X,入口點到相遇點的距離B->C是Z,設相遇點C到入口點B的距離C->B為Y.

4.slow走的路程為X+Z,fast走的路程為X+Z+N*(Z+Y)

5.因為fast是slow速度的兩倍,所以路程也是兩倍所以2(X+Z)=X+Z+N*(X+Y)

6.化簡X = (N-1)*(Z+Y)+Y 表示的是,從起始點到入口點的距離正好等于從相遇點開始走(N-1)個環的距離

7.結論:一個從頭走,一個從相遇點走,每個人走一步,相遇時,就是入口點.

畫圖決議:

代碼實作:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(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;
            if(fast == slow ) {
                break;//此時fast和slow都在相遇點
            }
        }
        slow = head;//讓slow指向頭 從頭開始
        while(fast !=slow){
            //一個人走一步
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/352288.html

標籤：其他

上一篇：SICNU ACM新生第一次考核

下一篇：第二天打卡-整數規劃（1）

初始Java , Java SE 十一道鏈表相關面試題,牛客 LeetCode,在線OJ題

鏈表面試題:

第一題 : 移除鏈表元素

解題思路:

畫圖決議:

具體代碼:

第二題 : 反轉鏈表

解題思路:

畫圖決議:

具體代碼:

第三題 : 鏈表的中間結點

解題思路:

畫圖決議:

具體代碼:

第四題 : 鏈表中倒數第k個結點

解題思路:

畫圖決議:

具體代碼:

第五題 : 合并兩個有序鏈表

解題思路:

畫圖決議:

具體代碼:

第六題 : 鏈表分割

解題思路:

畫圖決議:

具體代碼:

第七題 : 洗掉鏈表中重復的結點

解題思路:

畫圖決議:

代碼實作:

第八題 : 鏈表的回文結構

解題思路:

畫圖決議:

代碼實作:

第九題 : 相交鏈表

解題思路:

畫圖決議:

代碼實作:

第十題 : 環形鏈表

解題思路:

畫圖決議:

代碼實作:

十一題 : 環形鏈表 II

解題思路:

畫圖決議:

代碼實作: