Java 連結串列實戰真題訓練

2022-04-02 10:00:02

1、刪除值為val的所有節點
2、反轉連結串列
3、返回連結串列中間節點
4、返回連結串列第K個節點
5、合併有序連結串列
6、按值分割連結串列
7、判讀迴文連結串列
8、找兩個連結串列的公共節點
9、判斷成環連結串列
10、返回成環連結串列的入口

每個題目後面有放對應題目的OJ連結，大家可以先了解一下解題思路，然後自己先去做一下。

1、刪除值為val的所有節點

刪除連結串列中等於給定值val的所有節點。【OJ連結】

定義兩個指標prev、cur，cur指向頭節點的下一個節點，prev始終指向cur的前一個結點（方便刪除節點）。通過cur指標去遍歷連結串列，和val值比較，相同就刪除這個節點。最後再來比較頭節點。

/**
 * 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 prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

2、反轉連結串列

反轉一個連結串列。【OJ連結】

在遍歷連結串列時，將當前節點的指標改為指向前一個節點。由於節點沒有參照其前一個節點，因此必須事先儲存其前一個節點。在更改參照之前，還需要儲存後一個節點。最後返回新的頭參照。

/**
 * 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;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

3、返回連結串列中間節點

給定一個帶有頭節點的非空單連結串列，返回連結串列的中間節點。如果有兩個中間節點，則返回第二個中間節點。【OJ連結】

我們可以定義兩個快慢指標（fast、slow），都指向頭節點。快指標每次走兩步，慢指標每次走一步。連結串列有偶數個節點時，fast=null時slow為中間節點；連結串列有奇數個節點時，fast.next=null時slow為中間節點。

/**
 * 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 slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4、返回連結串列第K個節點

輸入一個連結串列，返回該連結串列中倒數第K個節點。【OJ連結】

這個題和找中間節點的思路相似。定義兩個指標（fast、slow）。在K合理的前提下，我們可以讓快指標先走K-1步，然後快慢指標同時向後走，當fast到達連結串列結尾時，slow就指向倒數第K個節點。

/*
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(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1>0){
            if(fast.next==null){
                return null;
            }
            fast=fast.next;
            //先讓快節點走k-1步
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
       
    }
}

5、合併有序連結串列

將兩個有序連結串列合併為一個有序連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。【OJ連結】

解這個題，需要定義虛假節點來充當新連結串列的頭節點。通過兩個連結串列的頭節點去遍歷兩個節點，去比較兩個連結串列對應節點的值，將值小的節點連線到新連結串列的後面，知道兩個連結串列遍歷完，當其中一個連結串列為空時，直接將另一個連結串列連線到新連結串列後面即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //建立虛擬節點，充當新連結串列的頭節點，值不代表任何意義
        ListNode node=new ListNode(-1);
        ListNode cur=node;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }else{
            cur.next=list1;
        }
        return node.next;
    }
}

6、按值分割連結串列

將一個連結串列按照給定值X劃分為兩部分，所有小於X的節點排在大於或等於X的節點之前。不改變節點原來的順序。【OJ連結】

首先我們需要定義四個指標（bs、be、as、ae）分別表示小於X部分連結串列的頭節點和尾節點、大於X部分連結串列的頭節點和尾節點。通過頭節點遍歷連結串列，將連結串列分為兩部分。最後將兩個連結串列連線起來即可。需要特別注意，當小於X部分連結串列不為空時，我們需要手動將ae.next置為空。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
            //如果小於X部分為空，則直接返回大於X部分即可。此時ae.next一定為null
        }
        be.next=as;//否則連線小於X和大於X部分
        if(as!=null){
           ae.next=null;
           //當小於X部分不為空時，ae.next可能不為null，需要手動置為null
        }
        return bs;
    }
}

7、判讀迴文連結串列

判斷連結串列是不是迴文連結串列。【OJ連結】

首先我們需要找到連結串列的中間節點，然後將後半段連結串列反轉。最後通過兩邊來逐步比較即可。特別注意，當連結串列結點個數為偶數時，因為中間節點的緣故，兩邊遍歷時，無法相遇，需要特殊處理。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
        //求連結串列的中間節點
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反轉後半段連結串列
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //判斷迴文連結串列
        while(slow!=A){
            if(slow.val!=A.val){
              return false;
           }
            if(A.next==slow){
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return true;
    }
}

8、找兩個連結串列的公共節點

輸入兩個連結串列，輸出兩個連結串列的第一個公共節點。沒有返回NULL。【OJ連結】

兩個連結串列相交呈現Y字型。那麼兩個連結串列長度的差肯定是未相交前兩個連結串列節點的差。我們需要求出兩個連結串列的長度。定義兩個指標（pl、ps），讓pl指向長的連結串列，ps指向短的連結串列。求出兩個連結串列的長度差len。讓pl想走len步。這樣兩個連結串列的剩餘長度就相同。此時兩個指標同時遍歷連個連結串列，如果其指向一致，則兩個連結串列相交，否則，兩個連結串列不相交。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //求連結串列長度
    public int len(ListNode head){
        int len=0;
        while(head!=null){
            head=head.next;
            len++;
        }
        return len;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pl=headA;
        ListNode ps=headB;
        int lenA=len(headA);
        int lenB=len(headB);
        int len=lenA-lenB;
        if(len<0){
            //pl指向長的連結串列，ps指向短的連結串列
            pl=headB;
            ps=headA;
            len=-len;
        }
        while(len--!=0){
            pl=pl.next;
        }
        while(pl!=null){
            if(pl==ps){
                return pl;
            }
            pl=pl.next;
            ps=ps.next;
        }
        return null;
    }
}

9、判斷成環連結串列

判斷連結串列中是否有環。【OJ連結】

還是快慢指標。慢指標一次走一步，快指標一次走兩步。兩個指標從連結串列起始位置開始執行。如果連結串列帶環則一定會在環中相遇，否則快指標率先走到連結串列的末尾。

【拓展】

/**
 * 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||head.next==null){
            return false;//連結串列為空或者只有一個節點時，沒有環
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
                //如果快慢節點可以相遇，表示連結串列有環
            }
        }
        return false;
    }
}

10、返回成環連結串列的入口

給定一個連結串列，判斷連結串列是否有環並返回入環的節點。如果沒有環，返回NULL。【OJ連結】

讓一個指標從連結串列的其實在位置開始遍歷，同時另一個指標從上題中兩隻真相與的位置開始走，兩個指標再次相遇時的位置肯定為環的入口

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //判斷連結串列是否有環，並返回第一次快慢節點相交的位置
    public ListNode hasCycle(ListNode head){
         if(head==null||head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               return slow;
            }
        }
        return null;
    }
    //當返回的結點與頭節點再次相交時，為環的入口
    public ListNode detectCycle(ListNode head) {
        ListNode node=hasCycle(head);
        if(node==null){
            return null;
        }else{
            while(head!=node){
                head=head.next;
                node=node.next;
            }
        }
        return head;
    }
}

到此這篇關於Java 連結串列實戰真題訓練的文章就介紹到這了,更多相關Java 連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！