關(guān)于 Java 的數(shù)據(jù)結(jié)構(gòu)鏈表

更新時(shí)間：2021年09月06日 15:42:38 作者：吞吞吐吐大魔王

這篇文章主要介紹了關(guān)于 Java 的數(shù)據(jù)結(jié)構(gòu)鏈表的相關(guān)資料,需要的朋友可以參考下面文章內(nèi)容

1. 刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)
2. 反轉(zhuǎn)一個(gè)單鏈表
3. 給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表
4. 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
5. 有序鏈表合并為一
6. 編寫(xiě)代碼
7. 刪除該鏈表中重復(fù)的結(jié)點(diǎn)
8. 鏈表的回文結(jié)構(gòu)
9. 輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)
10. 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)
11. 給定一個(gè)鏈表

數(shù)據(jù)結(jié)構(gòu)關(guān)于 Java 的鏈表

1. 刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)

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){
                cur=cur.next;
                prev.next=cur;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

2. 反轉(zhuǎn)一個(gè)單鏈表

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode cur=head;
        ListNode newHead=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=newHead;
            newHead=cur;
            cur=curNext;
        }
        return newHead;     
    }
}

方法： 頭插法（從第二個(gè)節(jié)點(diǎn)開(kāi)始對(duì)第一個(gè)節(jié)點(diǎn)進(jìn)行頭插）

注意：

逆置不是只將數(shù)值反轉(zhuǎn)，而是將節(jié)點(diǎn)本身進(jìn)行逆置

如果用前一章的 diplay 方法將逆置后的打印結(jié)果不正確，因?yàn)樵?diplay 方法是從一開(kāi)始定義的 head 節(jié)點(diǎn)開(kāi)始打印，而現(xiàn)在真正的頭節(jié)點(diǎn)已經(jīng)改變，可以將其修改一下
public void display2(Node newHead){
    Node cur = newHead;
    while(cur!=null){
        System.out.print(cur.val + " ");
        cur=cur.next;
    }
    System.out.println();
}

3. 給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表

給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)

方法一：通過(guò)遍歷找到節(jié)點(diǎn)數(shù)，然后找到中間節(jié)點(diǎn)

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        count=count/2+1;
        ListNode node=head;
        int i=0;
        while(i!=count-1){
            node=node.next;
            i++;
        }
        return node;
    }
}

方法二： 快慢指針?lè)ǎ熘羔樢淮巫邇刹剑羔樢淮巫咭徊剑?/p>

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4. 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

方法一：通過(guò)遍歷找到節(jié)點(diǎn)數(shù)，然后找到倒數(shù)第 k 個(gè)節(jié)點(diǎn)

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null){
            return null;
        }
        ListNode cur = head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        if(k<1 || k>count){
            return null;
        }
        ListNode node = head;
        int i=0;
        while(i!=count-k){
            node=node.next;
            i++;
        }
        return node;
    }
}

方法二： 快慢指針?lè)ǎㄏ茸尶熘羔樧?k-1 步，再讓快慢指針同時(shí)走）

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k<=0){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1!=0){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

5. 有序鏈表合并為一

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

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null && l2==null){
            return null;
        }
        if(l1==null && l2!=null){
            return l2;
        }
        if(l2==null && l1!=null){
            return l1;
        }
        ListNode node=new ListNode();
        ListNode head=node;
        while(l1!=null && l2!=null){
            while(l1!=null && l2!=null && l1.val<=l2.val){
                node.next=l1;
                node=node.next;
                l1=l1.next;
            }
            while(l1!=null && l2!=null && l1.val>l2.val){
                node.next=l2;
                node=node.next;
                l2=l2.next;
            }
        }
        if(l1!=null){
            node.next=l1;   
        }
        if(l2!=null){
            node.next=l2;
        }
        return head.next;
    }
}

6. 編寫(xiě)代碼

以給定值x為基準(zhǔn)將鏈表分割成兩部分，所有小于x的結(jié)點(diǎn)排在大于或等于x的結(jié)點(diǎn)之前

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode cur=pHead;
        ListNode as=null;
        ListNode ae=null;
        ListNode bs=null;
        ListNode be=null;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=bs;
                }else{
                    be.next=cur;
                    be=be.next;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=as;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;
    }
}

其中 bs、be、as、ae，分別為小于 x 和大于 x 的兩端的頭尾節(jié)點(diǎn)

7. 刪除該鏈表中重復(fù)的結(jié)點(diǎn)

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        ListNode node=new ListNode(0);
        ListNode newHead=node;
        ListNode cur=pHead;
        
        while(cur!=null){
            if(cur.next!=null && cur.val==cur.next.val){
                while(cur.next!=null && cur.val==cur.next.val){
                    cur=cur.next;
                }
                cur=cur.next;
            }else{
                newHead.next=cur;
                newHead=newHead.next;
                cur=cur.next;
            }
        }
        newHead.next=null;
        return node.next;
    }
}

8. 鏈表的回文結(jié)構(gòu)

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return true;
        }
        if(A.next==null){
            return true;
        }
        ListNode left=A;
        ListNode mid=A;
        ListNode right=A;
        while(right!=null && right.next!=null){
            right=right.next.next;
            mid=mid.next;
        }
        ListNode cur=mid.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=mid;
            mid=cur;
            cur=curNext;
        }
        while(mid!=left){
            if(mid.val!=left.val){
                return false;
            }
            if(left.next==mid){
                return true;
            }
            mid=mid.next;
            left=left.next;
        }
        return true;
    }
}

方法：

找中間節(jié)點(diǎn)
反轉(zhuǎn)中間節(jié)點(diǎn)之后的鏈表
將反轉(zhuǎn)鏈表頭尾進(jìn)行比較

9. 輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)

public class Solution {
    public int getLength(ListNode head){
        if(head==null){
            return 0;
        }
        int count=0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode cur1=headA;
        ListNode cur2=headB;
        int length1=getLength(headA);
        int length2=getLength(headB);
        int i=0;
        if(length1>=length2){
            while(i!=length1-length2){
                cur1=cur1.next;
                i++;
            }
        }else{
            while(i!=length2-length1){
                cur2=cur2.next;
                i++;
            }
        }
        while(cur1!=cur2){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return cur1;
    }
}

方法： 因?yàn)楣餐?jié)點(diǎn)之后，兩個(gè)鏈表的節(jié)點(diǎn)一樣長(zhǎng)。只要在共同節(jié)點(diǎn)之前，讓兩個(gè)鏈表移動(dòng)的節(jié)點(diǎn)與公共節(jié)點(diǎn)距離相等，再一步一步移動(dòng)即可

10. 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        if(head.next==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

方法： 快慢指針?lè)ǎㄍㄟ^(guò)快指針追擊慢指針，能追得上則有環(huán)）

11. 給定一個(gè)鏈表

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。如果鏈表無(wú)環(huán)，則返回 null

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null || fast.next==null){
            return null;
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }

重點(diǎn)： 上述題中 fast=head ，以及后面代碼含義就是找到公共節(jié)點(diǎn)之后，從該鏈表的頭節(jié)點(diǎn)，以及交點(diǎn)，一起一步一步移動(dòng)，當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，則為第一個(gè)公共節(jié)點(diǎn)

分析： 上述重點(diǎn)不懂點(diǎn)可以結(jié)合下圖分析理解

當(dāng)?shù)谝蝗妥飞蠒r(shí)：結(jié)論為 X=Y，所以?xún)蓚€(gè)節(jié)點(diǎn)每次移動(dòng)一步就可
當(dāng)?shù)?n 圈就追上時(shí)：結(jié)論為 X=Y+(n-1)C。因?yàn)閮蓚€(gè)節(jié)點(diǎn)移動(dòng)路程是一樣的，并且交點(diǎn)那個(gè)節(jié)點(diǎn)移動(dòng) n-1 圈后，再要走 Y 正好到了起始節(jié)點(diǎn)。所以?xún)蓚€(gè)節(jié)點(diǎn)每次移動(dòng)一步就可

到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)關(guān)于 Java 的鏈表詳情的文章就介紹到這了,更多相關(guān)數(shù)據(jù)結(jié)構(gòu)關(guān)于 Java 的鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！