Java鏈表怎么應(yīng)用

這篇文章主要講解了“Java鏈表怎么應(yīng)用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Java鏈表怎么應(yīng)用”吧！

1、刪除值為val的所有節(jié)點(diǎn)

刪除鏈表中等于給定值val的所有節(jié)點(diǎn)?！綩J鏈接】

定義兩個指針prev、cur，cur指向頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)，prev始終指向cur的前一個結(jié)點(diǎn)（方便刪除節(jié)點(diǎn)）。通過cur指針去遍歷鏈表，和val值比較，相同就刪除這個節(jié)點(diǎn)。最后再來比較頭節(jié)點(diǎn)。

/**
 * 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、反轉(zhuǎn)鏈表

反轉(zhuǎn)一個鏈表?！綩J鏈接】

在遍歷鏈表時，將當(dāng)前節(jié)點(diǎn)的 指針改為指向前一個節(jié)點(diǎn)。由于節(jié)點(diǎn)沒有引用其前一個節(jié)點(diǎn)，因此必須事先存儲其前一個節(jié)點(diǎn)。在更改引用之前，還需要存儲后一個節(jié)點(diǎn)。最后返回新的頭引用。

/**
 * 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、返回鏈表中間節(jié)點(diǎn)

給定一個帶有頭節(jié)點(diǎn)的非空單鏈表，返回鏈表的中間節(jié)點(diǎn)。如果有兩個中間節(jié)點(diǎn)，則返回第二個中間節(jié)點(diǎn)?！綩J鏈接】

我們可以定義兩個快慢指針（fast、slow），都指向頭節(jié)點(diǎn)。快指針每次走兩步，慢指針每次走一步。鏈表有偶數(shù)個節(jié)點(diǎn)時，fast=null時slow為中間節(jié)點(diǎn)；鏈表有奇數(shù)個節(jié)點(diǎn)時，fast.next=null時slow為中間節(jié)點(diǎn)。

/**
 * 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個節(jié)點(diǎn)

輸入一個鏈表，返回該鏈表中倒數(shù)第K個節(jié)點(diǎn)?！綩J鏈接】

這個題和找中間節(jié)點(diǎn)的思路相似。定義兩個指針（fast、slow）。在K合理的前提下，我們可以讓快指針先走K-1步，然后快慢指針同時向后走，當(dāng)fast到達(dá)鏈表結(jié)尾時，slow就指向倒數(shù)第K個節(jié)點(diǎn)。

/*
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;
            //先讓快節(jié)點(diǎn)走k-1步
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
       
    }
}

5、合并有序鏈表

將兩個有序鏈表合并為一個有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。【OJ鏈接】

解這個題，需要定義虛假節(jié)點(diǎn)來充當(dāng)新鏈表的頭節(jié)點(diǎn)。通過兩個鏈表的頭節(jié)點(diǎn)去遍歷兩個節(jié)點(diǎn)，去比較兩個鏈表對應(yīng)節(jié)點(diǎn)的值，將值小的節(jié)點(diǎn)連接到新鏈表的后面，知道兩個鏈表遍歷完，當(dāng)其中一個鏈表為空時，直接將另一個鏈表連接到新鏈表后面即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //創(chuàng)建虛擬節(jié)點(diǎn)，充當(dāng)新鏈表的頭節(jié)點(diǎn)，值不代表任何意義
        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的節(jié)點(diǎn)排在大于或等于X的節(jié)點(diǎn)之前。不改變節(jié)點(diǎn)原來的順序。【OJ鏈接】

首先我們需要定義四個指針（bs、be、as、ae）分別表示小于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)、大于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。通過頭節(jié)點(diǎn)遍歷鏈表，將鏈表分為兩部分。最后將兩個鏈表連接起來即可。需要特別注意，當(dāng)小于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;
           //當(dāng)小于X部分不為空時，ae.next可能不為null，需要手動置為null
        }
        return bs;
    }
}

7、判讀回文鏈表

判斷鏈表是不是回文鏈表。【OJ鏈接】

首先我們需要找到鏈表的中間節(jié)點(diǎn)，然后將后半段鏈表反轉(zhuǎn)。最后通過兩邊來逐步比較即可。特別注意，當(dāng)鏈表結(jié)點(diǎn)個數(shù)為偶數(shù)時，因?yàn)橹虚g節(jié)點(diǎn)的緣故，兩邊遍歷時，無法相遇，需要特殊處理。

/*
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;
        }
        //求鏈表的中間節(jié)點(diǎn)
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反轉(zhuǎn)后半段鏈表
        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、找兩個鏈表的公共節(jié)點(diǎn)

輸入兩個鏈表，輸出兩個鏈表的第一個公共節(jié)點(diǎn)。沒有返回NULL?！綩J鏈接】

兩個鏈表相交呈現(xiàn)Y字型。那么兩個鏈表長度的差肯定是未相交前兩個鏈表節(jié)點(diǎn)的差。我們需要求出兩個鏈表的長度。定義兩個指針（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、判斷成環(huán)鏈表

判斷鏈表中是否有環(huán)?！綩J鏈接】

還是快慢指針。慢指針一次走一步，快指針一次走兩步。兩個指針從鏈表起始位置開始運(yùn)行。如果鏈表帶環(huán)則一定會在環(huán)中相遇，否則快指針率先走到鏈表的末尾。

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

10、返回成環(huán)鏈表的入口

給定一個鏈表，判斷鏈表是否有環(huán)并返回入環(huán)的節(jié)點(diǎn)。如果沒有環(huán)，返回NULL?！綩J鏈接】

讓一個指針從鏈表的其實(shí)在位置開始遍歷，同時另一個指針從上題中兩只真相與的位置開始走，兩個指針再次相遇時的位置肯定為環(huán)的入口

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //判斷鏈表是否有環(huán)，并返回第一次快慢節(jié)點(diǎn)相交的位置
    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;
    }
    //當(dāng)返回的結(jié)點(diǎn)與頭節(jié)點(diǎn)再次相交時，為環(huán)的入口
    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鏈表怎么應(yīng)用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Java鏈表怎么應(yīng)用這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！