真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

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

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

我們一直強(qiáng)調(diào)成都網(wǎng)站建設(shè)、網(wǎng)站制作對(duì)于企業(yè)的重要性,如果您也覺(jué)得重要,那么就需要我們慎重對(duì)待,選擇一個(gè)安全靠譜的網(wǎng)站建設(shè)公司,企業(yè)網(wǎng)站我們建議是要么不做，要么就做好,讓網(wǎng)站能真正成為企業(yè)發(fā)展過(guò)程中的有力推手。專業(yè)網(wǎng)站設(shè)計(jì)公司不一定是大公司,創(chuàng)新互聯(lián)建站作為專業(yè)的網(wǎng)絡(luò)公司選擇我們就是放心。

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)）。通過(guò)cur指針去遍歷鏈表，和val值比較，相同就刪除這個(gè)節(jié)點(diǎn)。最后再來(lái)比較頭節(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鏈接】

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

在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的 指針改為指向前一個(gè)節(jié)點(diǎn)。由于節(jié)點(diǎn)沒(méi)有引用其前一個(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)。

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

/**
 * 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)。【OJ鏈接】

這個(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è)有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。【OJ鏈接】

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

解這個(gè)題，需要定義虛假節(jié)點(diǎn)來(lái)充當(dāng)新鏈表的頭節(jié)點(diǎn)。通過(guò)兩個(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
6、按值分割鏈表
將一個(gè)鏈表按照給定值X劃分為兩部分，所有小于X的節(jié)點(diǎn)排在大于或等于X的節(jié)點(diǎn)之前。不改變節(jié)點(diǎn)原來(lái)的順序?！綩J鏈接】
首先我們需要定義四個(gè)指針（bs、be、as、ae）分別表示小于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)、大于X部分鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。通過(guò)頭節(jié)點(diǎn)遍歷鏈表，將鏈表分為兩部分。最后將兩個(gè)鏈表連接起來(lái)即可。需要特別注意，當(dāng)小于X部分鏈表不為空時(shí)，我們需要手動(dòng)將ae.next置為空。
Java鏈表怎么應(yīng)用
/*
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
7、判讀回文鏈表
判斷鏈表是不是回文鏈表?！綩J鏈接】
首先我們需要找到鏈表的中間節(jié)點(diǎn)，然后將后半段鏈表反轉(zhuǎn)。最后通過(guò)兩邊來(lái)逐步比較即可。特別注意，當(dāng)鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，因?yàn)橹虚g節(jié)點(diǎn)的緣故，兩邊遍歷時(shí)，無(wú)法相遇，需要特殊處理。
Java鏈表怎么應(yīng)用
Java鏈表怎么應(yīng)用
/*
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)。沒(méi)有返回NULL?！綩J鏈接】
兩個(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è)指針從鏈表起始位置開(kāi)始運(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í)，沒(méi)有環(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)。如果沒(méi)有環(huán)，返回NULL?！綩J鏈接】
讓一個(gè)指針從鏈表的其實(shí)在位置開(kāi)始遍歷，同時(shí)另一個(gè)指針從上題中兩只真相與的位置開(kāi)始走，兩個(gè)指針再次相遇時(shí)的位置肯定為環(huán)的入口
Java鏈表怎么應(yīng)用
/**
 * 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;
    }
}
感謝各位的閱讀，以上就是“Java鏈表怎么應(yīng)用”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Java鏈表怎么應(yīng)用這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
            
            
                        

            新聞標(biāo)題：Java鏈表怎么應(yīng)用            

            文章URL：http://weahome.cn/article/pjsggo.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部