鏈表常見面試題( 建議收藏！！)

建議先點收藏~~ 防止走丟 加油加油！！

1.洗掉鏈表中等于給定值 val 的所有節點

題目： 在線OJ

思考：
①用 tmp 記錄當前節點，若 tmp 的下一個節點不為空且下一個節點的節點值等于給定的 val，則需要洗掉 tmp 的下一個節點—— tmp.next = tmp.next.next
②若 tmp 的下一節點值不等于 val，則保留下一個節點，并把 tmp 移到下一節點
③當 tmp 的下一節點為空時，鏈表遍歷結束，此時所有節點值為 val 的節點都被洗掉

代碼實作：

public Node deleteAllVal(Node head,int val){
	//考慮head為空的情況
	if(head == null){
		return null;
	}
	//tmp表示當前節點
	Node tmp = head;
	//cur表示待洗掉節點
	Node cur = head.next;
	while(cur != null){
		if(tmp.data == val){
			tmp.next = cur.next;
			cur = cur.next;
		}
		else{
			tmp = cur;
			cur = cur.next;
		}
	}
	if(head.data == val){
		head = head.next;
	}
	return head;
}

2.反轉一個單鏈表🔺

題目： 在線OJ

思考：
.

方法1 迭代

• 用 cur 表示當前需要反轉的節點
• 創建一個 prev，初始化為null，指向cur
• curNext 表示下一個需要反轉的節點
• 當 cur 為空的時候，表示鏈表遍歷結束 (回圈結束條件)
• 最后回傳 newHead

public Node reverseList(Node head){
    Node prev = null;
    Node cur = this.head;
    Node newHead = null;
    while (cur != null){
        Node curNext = cur.next;
        if(curNext == null){
            newHead = cur;
        }
        cur.next = prev;
        prev = cur;
        cur = curNext;
    }
    return newHead;
}

反轉結束后，不能再使用原來得 print 方法進行列印，因為它是從原來得 head 開始，而此時是 newHead，則需要重寫一個 newPrint 方法

新得 print 方法：

public static void newPrint(Node newHead){
    Node cur = newHead;
    while (cur != null){
        System.out.print(cur.data+" ");
        cur = cur.next; //節點后移
    }
    System.out.println();
}

方法2 利用頭插法

• 先將頭節點的 next 域置為null
• 將head之后的一個節點進行頭插法
• 以此類推，直到最后一個節點頭插結束后，則反轉完畢

public Node reverseList2(){
    if(this.head == null) {
        return null;
    }
    if(this.head.next == null) {
        return this.head;
    }
    Node cur = this.head.next;
    this.head.next = null;
    while (cur != null) {
        Node curNext = cur.next;
        this.addFist(cur.data);
        cur = curNext;
    }
    return this.head;
}

3.鏈表的中間節點

題目： 在線OJ

要求： 給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點；如果有兩個中間結點，則回傳第二個中間結點
.
即：

思考：

1. 定義一個兩個指標 fast、slow
2. slow 一次走一個節點，fast 一次走兩個節點
3. 當 fast 走完，即 fast.nest / fast 為 null 時，slow剛好指向 “中間節點”

核心： fast 的速度是 slow 的二倍

代碼實作：

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

4.鏈表中倒數第k個節點

題目： 在線OJ

思考：

• 創建兩個指標fast、slow，均指向 head節點
• 讓 fast 走 k-1步
• 然后slow 和 fast一起，一次走一步
• 當 fast 走完時，即 fast.nest 為 null 時，slow就指向倒數第k個節點

注意 k 的合法性判定

代碼實作：

public Node getKthFromEnd(int k) {
    //k 合法性判定
    if(k <= 0){
        System.out.println("k不合法！");
        return null;
    }
    Node fast = this.head;
    Node slow = this.head;
    while(k-1 > 0){
        if(fast.next != null){
            fast = fast.next;
            k--;
        }
        else {
            System.out.println("該節點不存在！");
            return null;
        }
    }
    while(fast.next != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

5.鏈表分割

題目： 在線OJ

思考：

• 創建兩個"線段"，兩個線段的頭 (bs、be) 尾 (as、ae) 均初始化為 null
• 定義 cur，遍歷原來的單鏈表
• 若 cur.data < x，則放到第一個線段
  若 cur.data > x，則放到第二個線段
  均采用尾插法
• 當 cur 為 null 時，原來的單鏈表就遍歷結束
• 最后將 be 和 as拼接，即：be.next = as

代碼實作：

public Node partition(int x) {
    Node bs = null;
    Node be = null;
    Node as = null;
    Node ae = null;
    Node cur = this.head;
    while(cur != null){
        if(cur.data < 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;
    }
    // 判斷 bs是否為空，若 bs==null，回傳as
    if(bs == null){
        return as;
    }
    be.next = as;
    //若 bs不為 null，需進行拼接
    if(ae != null){
        ae.next = null;
    }
    //若ae不為 null，ae的next需要置為null
    return bs;
}

6.洗掉排序鏈表中的重復元素

題目： 在線OJ

思考：定義一個虛擬節點來解決問題

• 首先定義一個虛擬節點newHead
• 使用 cur 遍歷鏈表，比較 cur.data 和 cur.next.data 是否相等
• 不相等，則將 cur節點，放置虛擬節點后
• 最后回傳 newHead.next 即可

代碼實作：

public Node deleteDuplicates() {
    //虛擬節點
    Node newHead = new Node(-1);
    Node cur = this.head;
    Node tmp = newHead;
    while(cur != null){
        if(cur.next != null && cur.data == cur.next.data){
            while(cur.next != null && cur.data == cur.next.data){
                cur = cur.next;
            }
            cur = cur.next;
        }
        else {
            tmp.next = cur;
            tmp = tmp.next;
            cur = cur.next;
        }
    }
    tmp.next = null;
    return newHead.next;
}

最后記得手動將 tmp.next 置為 null，否則可能陷入死回圈

7.回文鏈表🔺

題目： 在線OJ

思考：

• 先找到當前鏈表的中間節點
• 再反轉單鏈表的后半部分
• 一個從頭往后走，一個從尾往前走，依次比較

奇數個績點節點
.

.
偶數個節點

代碼實作：

public boolean isPalindrome() {
    //單鏈表為null
    if(this.head == null){
        return false;
    }
    //只有一個節點
    if(this.head.next == null){
        return true;
    }
    //找單鏈表的中間節點  回圈結束后 slow 即為中間節點
    Node fast = this.head;
    Node slow = this.head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //反轉單鏈表的后半部分 slow 為中間節點
    Node cur = slow.next;
    while(cur != null){
        Node curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //回圈結束，slow 為最后一個節點
    //一個從頭，一個從尾
    while(slow != this.head){
        if(slow.data != this.head.data){
            return false;
        }
        //偶數個節點
        if(this.head.next == slow){
            return true;
        }
        else{
            slow = slow.next;
            this.head = this.head.next;
        }
    }
    return true;
}

8.環形鏈表

題目： 在線OJ

思考：

• 定義 fast、slow
  fast一次走兩步，slow一次走一步
• 若有環，則一定相遇
  若無環，則不相遇

每走一步，判斷 slow 和 fast 是否相等，相等則有環
每走一步，都要進行判斷 fast==null / fast.next ==null，若存在，則沒有環

代碼實作：

public boolean hasCycle() {
    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;
}

9.環形鏈表Ⅱ

題目： 在線OJ

思考分析： 即回傳入環的地址
.

.

代碼實作：

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 = this.head;
    while(slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

10.相交鏈表

題目： 在線OJ

思考分析：

• 首先要知道兩個單鏈表的長度 lenA，lenB
• 計算兩單鏈表長度的差值
• 讓長的單鏈表先走 差值步
• 然后兩個一起往后走，進行比較

代碼實作：

public Node getIntersectionNode(Node headA,Node headB) {
    //求長度，走差值步
    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 = headA;
    pS = headB;
    int len = lenA - lenB;
    //讓pL指向長的
    if(len < 0){
        pL = headB;
        pS = headA;
        len = lenB - lenA;
    }
    //讓pL先走len步
    for (int i = 0; i < len; i++) {
        pL = pL.next;
    }
    //pL pS一起走
    while(pS != pL && pS != null && pL != null){
        pS = pS.next;
        pL = pL.next;
    }
    if(pL == pS && pL != null){
        return pL;
    }
    return null;
}

11.合并兩個有序鏈表

題目： 在線OJ

思考分析：
.
最終結果：
.

程序：

• ①先比較 headA.data 和 headB.data 的大小，誰小誰先利用尾插法插入到虛擬節點后(以headA小為例)
• ②將headA后移，再進行比較，再將小的繼續使用尾插法挪，以此類推

.

代碼實作：

public Node mergeTwoLists(Node headA,Node headB) {
    //虛擬節點
    Node newHead = new Node(-1);
    Node tmp = newHead;
    while(headA != null && headB != null){
        if(headA.data < headB.data){
            tmp.next = headA;
            tmp = tmp.next;
            headA = headA.next;
        }
        else{
            tmp.next = headB;
            tmp = tmp.next;
            headB = headB.next;
        }
    }
    if(headA != null){
        tmp.next = headA;
    }
    if(headB != null){
        tmp.next = headB;
    }
    return newHead.next;
}

歡迎大家一起探討學習~