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：
??核心代碼：
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 ，請你反轉鏈表，并回傳反轉后的鏈表，
什么是反轉鏈表？
但是我們可以用另外一種方式看
📝大體思路：
反轉鏈表可以采用頭插法的方式，鏈表的最后next域是一個null，所以我們就把第一個節點next域設成null，curNext的參考變數記錄下一個節點，再用cur參考變數指向當前節點，用prev改變next域，使方向反轉
??核心代碼：
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
??核心代碼：
while(fast!=null && fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
}
注意細節：
如果有兩個中間結點，則回傳第二個中間結點，
💬完整代碼：
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，
??核心代碼：
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，同理，最后回傳傀儡節點，
??核心代碼：
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，
??核心代碼：
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停下來
??核心代碼：
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，避免程式錯誤
💬完整代碼：
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一起走直到相遇停止，
??核心代碼：
//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就好了，不然按照正常執行代碼是會出現錯誤
💬完整代碼：
//鏈表回文
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的速度快一倍，如果他們相遇就有環，不能相遇無環，
??核心代碼：
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，
📝大體思路：
需要一個公式證明一個結論，看圖說話，
有圖可知：
由這個公式可以推出，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 ，
📝大體思路：
話語不變描述，還是看圖說話吧
如果是上面這種形式，相交之前都是相同的節點個數，就比較簡單，兩個鏈表直接定義兩個參考變數，pl和ps，回圈，直到pl==ps就找到公共節點，
??核心代碼：
while(pl!=ps) {
pl=pl.next;
ps=ps.next;
}
//最終都沒有相交都回傳null，這段代碼寫不寫都沒問題
if(pl==null && ps==null) {
return null;
}
return ps;
如果是上面這種形式，我們就要想辦法，讓相交之前走的節點數相同，所以，首先計算相交之前兩個鏈表的節點個數，然后像個鏈表相交之前的節點個數之差，就是長鏈表應該先走多少步，然后再一起走，直到相交，
💬完整代碼：
//兩個鏈表，找出他們的第一個公共節點
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299337.html
標籤：其他