0J面試題連結清單

文章目錄

0J面試題連結清單
- 一、單連結清單
- - 1.1删除連結清單中等于給定值val的所有節點
  - 1.2反轉一個單連結清單
  - 1.3連結清單的中間結點
  - 1.4連結清單中倒數第k個節點
  - 1.5合并兩個有序連結清單
  - 1.6連結清單分割
  - 1.7删除連結清單中重複的節點
  - 1.8連結清單的回文結構
  - 1.9環形連結清單
  - 2.0 環形連結清單 ||
  - 2.1相交連結清單

一、單連結清單

1.1删除連結清單中等于給定值val的所有節點

OJ連結

📜描述：

給你一個連結清單的頭節點

head

和一個整數

val

，請你删除連結清單中所有滿足

Node.val == val

的節點，并傳回新的頭節點。

📝大體思路：

定義一個引用變量cur來判斷目前節點是否為删除的值的節點，在定義prev，是cur的前驅，用來跳過删除的值的節點

假設跳過的val是8：

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

if(cur.val == val) {
       prev.next = cur.next;
       cur = cur.next;
      }else {
       prev = cur;
       cur = cur.next;
  }

注意的細節：

1、head不能為空。

2、如果删除的值是第一個，那就放在最後處理

💬完整代碼：

public void removeAllKey(int val) {
        if(this.head == null) {//head不能為空。
            return;
        }
        Node prev = this.head;
        Node cur = this.head.next;
        while (cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最後判斷頭節點
        if(this.head.val == val) {
            this.head = this.head.next;
        }
    }

1.2反轉一個單連結清單

OJ連結

📜描述：

給你單連結清單的頭節點

head

，請你反轉連結清單，并傳回反轉後的連結清單。

什麼是反轉連結清單？

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

但是我們可以用另外一種方式看

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

📝大體思路：

反轉連結清單可以采用頭插法的方式，連結清單的最後next域是一個null，是以我們就把第一個節點next域設成null，curNext的引用變量記錄下一個節點，再用cur引用變量指向目前節點，用prev改變next域，使方向反轉

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

while(cur != null) {
            Node curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }

注意細節：

1.因為反轉設第一個節點next域設為空，是以newHead先設為null

2.如果隻有一個節點head或沒有節點直接傳回head

完整代碼：

public Node reverseList() {
        if(head == null||head.next == null)
            return head;

        Node cur = head;
        Node newHead = null;

        while(cur != null) {
            Node curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        return newHead;
    }

1.3連結清單的中間結點

OJ連結

📜描述：

給定一個頭結點為

head

的非空單連結清單，傳回連結清單的中間結點。

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

這道題比較簡單，

📝大體思路：

舉個例子，兩個同學比賽400m，一個同學是另一個同學速度的兩倍，快的同學跑到終點的時候，慢的同學剛好跑到了200m，正好是整個跑道的中點，是以我們也new一個fast和slow的引用變量，使fast速度是slow的兩倍，使他多走一步，fast走到null，傳回slow

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

while(fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }

注意細節：

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

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

💬完整代碼：

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

1.4連結清單中倒數第k個節點

OJ連結

📜描述

輸入一個連結清單，輸出該連結清單中倒數第k個結點。

我們隻需要周遊一遍連結清單

📝大體思路：

我們還是new一個fast和一個slow，fast和slow始終差k-1步，當fast走到了k-1步的時候，fast和slow一起走，直到fast為null，傳回slow。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

while( k-1 != 0) {
            if(fast.next != null) {
                fast = fast.next;
                k--;
            }else{
                return null;
            }
        }

        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;

注意細節：

1、head為空直接傳回null；

2、判斷k合不合法，k超過了總連結清單長度我們直接在k-1！=0直接限制，隻需要判斷k<0即可；

完整代碼：

public Node findKthToTail(int k) {
        if(head == null) return null;
        if(k < 0 ) {
            return null;
        }

        Node fast = head;
        Node slow = head;

        while( k-1 != 0) {
            if(fast.next != null) {
                fast = fast.next;
                k--;
            }else{
                return null;
            }
        }

        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

1.5合并兩個有序連結清單

OJ連結

📜描述：

将兩個升序連結清單合并為一個新的升序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

📝大體思路：

定義一個傀儡節點，和tmp引用變量指向這個傀儡對象，使兩個連結清單headA,headB互相比較，誰小就把他放在傀儡節點的後面，tmp指向最新的節點，循環；最後如果tmp在headB連結清單中next域為null，直接tmp的下一個節點直接指向headA，反之headA，同理。最後傳回傀儡節點。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }

注意細節：

傀儡節點可以指派負數，不影響

💬完整代碼：

public static Node mergeTwoLists (Node headA, Node headB){
        if (headA == null) return headB;
        if (headB == null) return headA;
        if (headA == null && headB == null) return null;

        Node newH = new Node(0);
        Node tmp = newH;

        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }
        if (headB == null) {
            tmp.next = headA;
        }
        if (headA == null) {
            tmp.next = headB;
        }
        return newH;
    }

1.6連結清單分割

OJ連結

📜描述

現有一連結清單的頭指針 Head，給一定值x，編寫一段代碼将所有小于x的結點排在其餘結點之前，且不能改變原來的資料順序，傳回重新排列後的連結清單的頭指針。

📝大體思路：

最後分割順序保持不變，是以可以采用尾插法的思想。

竟然是連結清單分割那我們就可以分為兩段一段是<x的，另一段是>=x的，第一段定義起點bs和終點be，另一段as和ae，他們都設定為null，cur這個引用變量每次與x比較，将<x放左邊，bs始終保持不變，be随着變化往後移，>x放右邊，反之同理，最後串起來就ok。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

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;

注意細節：

考慮如果連結清單全<x的時候，第二段就沒有，as就是null直接傳回第一段就行了，

如果>x的時候，那麼第一段就沒有節點，傳回第二段as，

💬完整代碼：

public Node partition( int x) {

        Node cur = this.head;
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;

        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;
        }
        //bs!=null
        be.next = as;
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
  /*if(bs == null) {
            return as;
        }else {
            be.next = as;
            ae.next = null;//注意問題，ae可能為空
            return bs;
        }*/

1.7删除連結清單中重複的節點

OJ連結

📜描述

在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。例如，連結清單1->2->3->3->4->4->5 處理後為 1->2->5

📝大體思路：

定義cur引用變量，如果目前val域與下一個節點val域相同就讓他跳過下個節點，如果是多個挨在一起的就使用循環，循環結束cur還在重複的節點上，是以多走一步；如果節點不重複，定義一個傀儡節點和tmp引用變量，cur用來判斷是否為重複節點，不是則tmp的next域等于cur，cur直到為null停下來

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

while (cur != null) {
    //cur.next != null : 判斷是不是隻有一個節點 或者 是不是尾巴節點
           if(cur.next != null && cur.val == cur.next.val) {
                //cur再走的過程當中，有可能剩下的都是相同的
                while ( cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;//多走一步

注意細節：

1、循環結束，要多走一步;

2、萬一隻有一個節點cur.next為空，會出現空指針異常，是以要加上cur.next!=null;

3、如果連結清單都重複也要加上cur.next!=null,避免空指針異常

4、最後tmp需要手動設定null，有可能不是null，避免程式錯誤

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

💬完整代碼：

public Node deleteDuplication() {

        Node newHead = new Node(-1);
        Node tmp = newHead;
        Node cur = this.head;
        while (cur != null) {
            //cur.next != null : 判斷是不是隻有一個節點 或者 是不是尾巴節點
            if(cur.next != null && cur.val == cur.next.val) {
                //cur再走的過程當中，有可能剩下的都是相同的
                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;
    }

1.8連結清單的回文結構

OJ連結

📜描述

對于一個連結清單，請設計一個時間複雜度為O(n),額外空間複雜度為O(1)的算法，判斷其是否為回文結構。

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

測試樣例：

1->2->2->1

傳回：true

📝大體思路：

快慢指針+反轉，1.2和1.3的結合，總體來說掌握中間節點和反轉連結清單，就會很簡單,反轉完畢後，slow和head一起走直到相遇停止。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

//1、找中間節點
        Node slow = this.head;
        Node fast = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow 指向的節點 就是中間節點
        //2、進行翻轉
        Node cur = slow.next;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

注意細節：

如果回文結構是1->2->2->1，最後一起走的時候head的next域等于slow就好了，不然按照正常執行代碼是會出現錯誤

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

💬完整代碼：

//連結清單回文
    public boolean chkPalindrome() {
        if(this.head == null) {
            return true;
        }
        if(this.head.next == null) {
            //隻有一個節點
            return true;
        }
        //1、找中間節點
        Node slow = this.head;
        Node fast = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow 指向的節點 就是中間節點
        //2、進行翻轉
        Node cur = slow.next;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //翻轉完畢 slow指的地方就是 最後一個節點
        while (slow != head) {
            if(slow.val != head.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

1.9環形連結清單

OJ連結

📜描述：

給定一個連結清單，判斷連結清單中是否有環。

📝大體思路：

也是需要用到快慢指針思想，fast比slow的速度快一倍，如果他們相遇就有環，不能相遇無環。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

❗️核心代碼：

fast = fast.next.next;
slow = slow.next;

注意細節：

為什麼fast走兩步而不是三步，因為會錯過與slow的最佳相遇時機，走兩步剛剛好

💬完整代碼：

//連結清單是否有環
    public boolean hasCycle1() {
        Node fast = this.head;
        Node slow = this.head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }

2.0 環形連結清單 ||

OJ連結

📜描述

給定一個連結清單，傳回連結清單開始入環的第一個節點。如果連結清單無環，則傳回

null

。

📝大體思路：

需要一個公式證明一個結論，看圖說話。

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

有圖可知：

由這個公式可以推出，x的路程==y的路程，就可以寫代碼了

❗️核心代碼：

while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }

注意細節：

break跳出來的時候，有可能是不滿足循環條件跳出來的，也有可能是條件語句跳出來的

💬完整代碼：

//給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null
    public Node detectCycle() {
        Node fast = this.head;
        Node slow = this.head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }

        if(fast == null || fast.next == null) {
            return null;
        }

        //slow和fast是相遇的
        slow = this.head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

2.1相交連結清單

OJ連結

📜描述：

給你兩個單連結清單的頭節點

headA

和

headB

，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單沒有交點，傳回

null

。

📝大體思路：

話語不變描述，還是看圖說話吧

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

如果是上面這種形式，相交之前都是相同的節點個數，就比較簡單，兩個連結清單直接定義兩個引用變量，pl和ps，循環，直到pl==ps就找到公共節點。

❗️核心代碼：

while(pl!=ps) {
            pl=pl.next;
            ps=ps.next;
        }
        //最終都沒有相交都傳回null，這段代碼寫不寫都沒問題
        if(pl==null && ps==null) {
            return null;
        }
        return ps;

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

如果是上面這種形式，我們就要想辦法，讓相交之前走的節點數相同，是以，首先計算相交之前兩個連結清單的節點個數，然後像個連結清單相交之前的節點個數之差，就是長連結清單應該先走多少步，然後再一起走，直到相交。

💬完整代碼：

//兩個連結清單，找出他們的第一個公共節點
    public static Node getIntersectionNode(Node headA, Node headB) {
        if(headA==null) return null;
        if(headB==null) return null;

        int lenA=0;//用來計算相交之前的長度
        int lenB=0;//用來計算相交之前的長度

        Node pl=headA;
        Node ps=headB;

        while(pl!=null) {
            lenA++;
            pl=pl.next;
        }
        while(ps!=null) {
            lenB++;
            ps=ps.next;
        }
        //走出來pl和ps都為null
        pl=headA;
        ps=headB;
        //<   ==   >
        int len=lenA-lenB;
        //：pl永遠指向的是長的連結清單   ps永遠指向短的連結清單   len永遠是一個正數
        if(len<0) {
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }
//長連結清單先走的步數
        while(len!=0) {
            pl=pl.next;
            len--;
        }

        while(pl!=ps) {
            pl=pl.next;
            ps=ps.next;
        }
        //最終都沒有相交都傳回null，這段代碼寫不寫都沒問題
        if(pl==null && ps==null) {
            return null;
        }
        return ps;
    }

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

0J面試題連結清單

文章目錄

一、單連結清單

1.1删除連結清單中等于給定值val的所有節點

1.2反轉一個單連結清單

1.3連結清單的中間結點

1.4連結清單中倒數第k個節點

1.5合并兩個有序連結清單

1.6連結清單分割

1.7删除連結清單中重複的節點

1.8連結清單的回文結構

1.9環形連結清單

2.0 環形連結清單 ||

2.1相交連結清單

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題 連結清單

0J面試題 連結清單

文章目錄

一、單連結清單

1.1删除連結清單中等于給定值val的所有節點

1.2反轉一個單連結清單

1.3連結清單的中間結點

1.4連結清單中倒數第k個節點

1.5合并兩個有序連結清單

1.6連結清單分割

1.7删除連結清單中重複的節點

1.8連結清單的回文結構

1.9環形連結清單

2.0 環形連結清單 ||

2.1相交連結清單

繼續閱讀

java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題連結清單

0J面試題連結清單