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

更新時間：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)一個單鏈表
3. 給定一個帶有頭結(jié)點(diǎn) head 的非空單鏈表
4. 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)
5. 有序鏈表合并為一
6. 編寫代碼
7. 刪除該鏈表中重復(fù)的結(jié)點(diǎn)
8. 鏈表的回文結(jié)構(gòu)
9. 輸入兩個鏈表，找出它們的第一個公共結(jié)點(diǎn)
10. 給定一個鏈表，判斷鏈表中是否有環(huán)
11. 給定一個鏈表

數(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)一個單鏈表

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;     
    }
}

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

注意：

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

如果用前一章的 diplay 方法將逆置后的打印結(jié)果不正確，因為該 diplay 方法是從一開始定義的 head 節(jié)點(diǎn)開始打印，而現(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. 給定一個帶有頭結(jié)點(diǎn) head 的非空單鏈表

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

方法一：通過遍歷找到節(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;
    }
}

方法二： 快慢指針法（快指針一次走兩步，慢指針一次走一步）

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. 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)

方法一：通過遍歷找到節(jié)點(diǎn)數(shù)，然后找到倒數(shù)第 k 個節(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;
    }
}

方法二： 快慢指針法（先讓快指針走 k-1 步，再讓快慢指針同時走）

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. 有序鏈表合并為一

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(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. 編寫代碼

以給定值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)

在一個排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請刪除該鏈表中重復(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. 輸入兩個鏈表，找出它們的第一個公共結(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;
    }
}

方法： 因為共同節(jié)點(diǎn)之后，兩個鏈表的節(jié)點(diǎn)一樣長。只要在共同節(jié)點(diǎn)之前，讓兩個鏈表移動的節(jié)點(diǎn)與公共節(jié)點(diǎn)距離相等，再一步一步移動即可

10. 給定一個鏈表，判斷鏈表中是否有環(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;
    }
}

方法： 快慢指針法（通過快指針追擊慢指針，能追得上則有環(huán)）

11. 給定一個鏈表

給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。如果鏈表無環(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)兩個節(jié)點(diǎn)相遇時，則為第一個公共節(jié)點(diǎn)

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

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

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