Java鏈表實(shí)例分析

這篇文章主要介紹了Java鏈表實(shí)例分析的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Java鏈表實(shí)例分析文章都會(huì)有所收獲，下面我們一起來看看吧。

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

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

定義兩個(gè)指針prev、cur，cur指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，prev始終指向cur的前一個(gè)結(jié)點(diǎn)（方便刪除節(jié)點(diǎn)）。通過cur指針去遍歷鏈表，和val值比較，相同就刪除這個(gè)節(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)一個(gè)鏈表?！綩J鏈接】

在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的 指針改為指向前一個(gè)節(jié)點(diǎn)。由于節(jié)點(diǎn)沒有引用其前一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)節(jié)點(diǎn)。在更改引用之前，還需要存儲(chǔ)后一個(gè)節(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)

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

我們可以定義兩個(gè)快慢指針（fast、slow），都指向頭節(jié)點(diǎn)?？熘羔樏看巫邇刹剑羔樏看巫咭徊?。鏈表有偶數(shù)個(gè)節(jié)點(diǎn)時(shí)，fast=null時(shí)slow為中間節(jié)點(diǎn)；鏈表有奇數(shù)個(gè)節(jié)點(diǎn)時(shí)，fast.next=null時(shí)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個(gè)節(jié)點(diǎn)

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

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

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

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

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、按值分割鏈表

將一個(gè)鏈表按照給定值X劃分為兩部分，所有小于X的節(jié)點(diǎn)排在大于或等于X的節(jié)點(diǎn)之前。不改變節(jié)點(diǎn)原來的順序。【OJ鏈接】

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

7、判讀回文鏈表

判斷鏈表是不是回文鏈表?！綩J鏈接】

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

/*
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、找兩個(gè)鏈表的公共節(jié)點(diǎn)

輸入兩個(gè)鏈表，輸出兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)。沒有返回NULL。【OJ鏈接】

兩個(gè)鏈表相交呈現(xiàn)Y字型。那么兩個(gè)鏈表長(zhǎng)度的差肯定是未相交前兩個(gè)鏈表節(jié)點(diǎn)的差。我們需要求出兩個(gè)鏈表的長(zhǎng)度。定義兩個(gè)指針（pl、ps），讓pl指向長(zhǎng)的鏈表，ps指向短的鏈表。求出兩個(gè)鏈表的長(zhǎng)度差len。讓pl想走len步。這樣兩個(gè)鏈表的剩余長(zhǎng)度就相同。此時(shí)兩個(gè)指針同時(shí)遍歷連個(gè)鏈表，如果其指向一致，則兩個(gè)鏈表相交，否則，兩個(gè)鏈表不相交。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //求鏈表長(zhǎng)度
    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指向長(zhǎng)的鏈表，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鏈接】

還是快慢指針。慢指針一次走一步，快指針一次走兩步。兩個(gè)指針從鏈表起始位置開始運(yùn)行。如果鏈表帶環(huán)則一定會(huì)在環(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;//鏈表為空或者只有一個(gè)節(jié)點(diǎn)時(shí)，沒有環(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)鏈表的入口

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

讓一個(gè)指針從鏈表的其實(shí)在位置開始遍歷，同時(shí)另一個(gè)指針從上題中兩只真相與的位置開始走，兩個(gè)指針再次相遇時(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)再次相交時(shí)，為環(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;
    }
}

關(guān)于“Java鏈表實(shí)例分析”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“Java鏈表實(shí)例分析”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。