JAVA-高頻面試題匯總:鏈表

前言

為了讓小伙伴們更好地刷題,我將所有leetcode常考題按照知識點進行了歸納，

高頻題匯總:

JAVA-高頻面試題匯總:動態規劃
JAVA-高頻面試題匯總:字串
JAVA-高頻面試題匯總:二叉樹(上)
JAVA-高頻面試題匯總:二叉樹(下)
JAVA-高頻面試題匯總:回溯

JAVA-高頻面試題匯總:鏈表

接下來還會進行其他模塊的總結,有一起在準備暑期實習的JAVA后端的伙伴可以一起交流!
小編微信: Apollo___quan

目錄

1. 反轉鏈表（劍指）
2. 反轉鏈表 II
3. 兩個鏈表的第一個公共節點（劍指）
4. 兩個鏈表的第一個公共節點（劍指）
5. 合并兩個排序的鏈表
6. 合并K個升序鏈表
7. 從尾到頭列印鏈表
8. 鏈表中倒數第k個節點
9. 洗掉鏈表的節點（劍指）
10. 洗掉排序鏈表中的重復元素
11. 洗掉鏈表中重復的結點(劍指)
12. 復雜鏈表的復制（劍指）

1.反轉鏈表（劍指）

思路

雙指標，pre和cur

class Solution {
    public ListNode reverseList(ListNode head) {
            if(head == null) return null;
            ListNode pre = null, cur = head, next; //注意pre初始化null
            while(cur != null){
                next = cur.next; //暫存后繼節點
                cur.next = pre;
                pre = cur;
                cur = next;  
            }
            return pre;
    }
}

2.反轉鏈表 II

思路

1.con定位到m前一個，tail第m個，m~n就當作普通的鏈表反轉，然后更改con和tail的指標即可，

2.需要注意con可能為null，當m=1時

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        // Empty list
        if (head == null) {
            return null;
        }

        // Move the two pointers until they reach the proper starting point
        // in the list.
        ListNode cur = head, prev = null;
        while (m > 1) {
            prev = cur;
            cur = cur.next;
            m--;
            n--;
        }

        ListNode con = prev, tail = cur;   //con和tail為了之后連接

        ListNode third = null;
        while (n > 0) {    //對m~n中間的進行反轉
            third = cur.next;
            cur.next = prev;
            prev = cur;
            cur = third;
            n--;
        }
            //根據con和tail調整連接
        if (con != null) {       //注意con可能為null，當m=1時  
            con.next = prev;
        } else {
            head = prev;
        }

        tail.next = cur;
        return head;
    }
}

3.兩個鏈表的第一個公共節點（劍指）

思路

雙指標，在第一個交點必相遇（走過的路徑都等于A+B+公共）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1=headA;
        ListNode cur2=headB;
        while(cur1!=cur2){
           if(cur1==null) //cur1從A走完從B起點
           cur1=headB; 
           else{cur1=cur1.next;}
         if(cur2==null) cur2=headA; //cur2從B走完從A起點
         else
         cur2=cur2.next;
        }
        return cur1;
    }
}

4. 兩個鏈表的第一個公共節點（劍指）

思路

設定快慢指標，都從鏈表頭出發，快指標每次走兩步，慢指標一次走一步，假如有環，一定相遇于環中某點(結論1)，接著讓兩個指標分別從相遇點和鏈表頭出發，兩者都改為每次走一步，最終相遇于環入口(結論2)，以下是兩個結論證明：

1、設定快慢指標，假如有環，他們最后一定相遇，

2、兩個指標分別從鏈表頭和相遇點繼續出發，每次走一步，最后一定相遇與環入口，

證明結論1：設定快慢指標fast和low，fast每次走兩步，low每次走一步，假如有環，兩者一定會相遇（因為low一旦進環，可看作fast在后面追趕low的程序，每次兩者都接近一步，最后一定能追上），

證明結論2：

設：

鏈表頭到環入口長度為–a

環入口到相遇點長度為–b

相遇點到環入口長度為–c

則：相遇時

快指標路程=a+(b+c)k+b ，k>=1 其中b+c為環的長度，k為繞環的圈數（k>=1,即最少一圈，不能是0圈，不然和慢指標走的一樣長，矛盾），

慢指標路程=a+b

快指標走的路程是慢指標的兩倍，所以：

（a+b）*2=a+(b+c)k+b

化簡可得：

a=(k-1)(b+c)+c 這個式子的意思是： 鏈表頭到環入口的距離=相遇點到環入口的距離+（k-1）圈環長度，其中k>=1,所以k-1>=0圈，所以兩個指標分別從鏈表頭和相遇點出發，最后一定相遇于環入口，

public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(true){
            if(fast == null || fast.next == null|| fast.next.next == null) return null;
            fast=fast.next.next; 
            slow=slow.next;
            if(fast==slow) break; //第一次相遇時跳出
        }
        fast=pHead; //快指標從頭開始走
        while(true){
            if(fast==slow) return fast;  //快指標必定在入口處與慢指標再相遇
            fast=fast.next; 
            slow=slow.next;
        }   
    }

5.合并兩個排序的鏈表

思路

引入偽頭節點list，節點tar指向list

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode list=new ListNode();
        ListNode tar=list;
       while(l1!=null&&l2!=null){
         if(l1.val<=l2.val) {
             tar.next=l1;
             l1=l1.next;
         }
         else{
             tar.next=l2;
             l2=l2.next;
         }
         tar=tar.next;
       }
      tar.next=l1!=null?l1:l2; //將剩下的拼接
       return list.next;
    }

6.合并K個升序鏈表

思路

一、小根堆

先將k個鏈表頭節點輸入小根堆，然后創建新串列，插入小根堆的poll（最小的出隊），將其下一個節點再入小根堆（排序）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val); //重寫比較器，引數傳為節點的值
        for (ListNode node: lists) {
            if (node != null) {
                pq.offer(node); //將鏈表頭加入
            }
        }

        ListNode dummyHead = new ListNode(0); //新鏈表
        ListNode tail = dummyHead;  //tail作為指標
        while (!pq.isEmpty()) { 
            ListNode minNode = pq.poll();  //取出優先級佇列中最小的
            tail.next = minNode; //最小值插入新鏈表
            tail = minNode;
            if (minNode.next != null) {  
                pq.offer(minNode.next);  //將最小值的下一個值插進優先級佇列中排序
            }
        }
        return dummyHead.next;
    }
}

二、兩兩合并對 1 進行優化，時間復雜度：O(NlogK)

時間復雜度分析：KK 條鏈表的總結點數是 NN，平均每條鏈表有 N/KN/K 個節點，因此合并兩條鏈表的時間復雜度是 O(N/K)O(N/K)，從 KK 條鏈表開始兩兩合并成 11 條鏈表，因此每條鏈表都會被合并 logKlogK 次，因此 KK 條鏈表會被合并 K * logKK?logK 次，因此總共的時間復雜度是 KlogKN/KK?logK?N/K 即 O（NlogK）O（NlogK），

 public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        int k = lists.length;
        while (k > 1) {
            int idx = 0;
            for (int i = 0; i < k; i += 2) {
                if (i == k - 1) {
                    lists[idx++] = lists[i];
                } else {
                    lists[idx++] = merge2Lists(lists[i], lists[i + 1]);  //merge2Lists為合并兩個有序鏈表
                }
            }
            k = idx;
        }
        return lists[0];
    }

7.從尾到頭列印鏈表

思路

輔助堆疊法

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        while(head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.pop();
    return res;
    }
}

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

思路

雙指標，前面的former先走k，再latter和former同時走，

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

9.洗掉鏈表的節點（劍指）

思路

只有需要找到并洗掉一個值，用cur定位改值，讓pre.next = cur.next即可

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) { //跳出回圈時cur.val == val
            pre = cur;
            cur = cur.next;
        }
        if(cur != null) pre.next = cur.next; //相當于跳過cur
        return head;
    }
}

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

思路

判斷current和current.next是否相等，相等則current.next指向current.next.next

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) { //如果重復，則next指向next.next
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

11.洗掉鏈表中重復的結點(劍指)

思路

1.構造pre和cur,初始化時pre.next = pHead，構造了偽頭節點

2.當cur.next == cur,則不斷cur = cur.next，跳出回圈時cur是最后一個重復數，仍需處理 cur = cur.next, pre.next = cur;

public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null || pHead.next == null){
            return pHead;
        }
        // 自己構建輔助頭結點
        ListNode head = new ListNode(0); //構造鏈表頭
        ListNode pre = head;
        head.next = pHead;  //鏈表頭下一個才是Head，便于討論pHead重復的情況
        ListNode cur = pHead;
        while(cur!=null){
            if(cur.next != null && cur.next.val == cur.val){
                // 相同結點一直前進
                while(cur.next != null && cur.next.val == cur.val){
                    cur = cur.next;
                }
                // 退出回圈時，cur 指向重復值，也需要洗掉，而 cur.next 指向第一個不重復的值
                // cur 繼續前進
                cur = cur.next;
                // pre 連接新結點
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
}

12.復雜鏈表的復制（劍指）

思路

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 復制各節點，并建立 “原節點 -> 新節點” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 構建新鏈表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 回傳新鏈表的頭節點
        return map.get(head);
    }
}

總結

鏈表題型整理完畢，其余型別
JAVA-高頻面試題匯總:動態規劃
JAVA-高頻面試題匯總:字串
JAVA-高頻面試題匯總:二叉樹(上)
JAVA-高頻面試題匯總:二叉樹(下)
JAVA-高頻面試題匯總:回溯