歡迎關(guān)注個人主頁：逸狼

---

創(chuàng)造不易，可以點點贊嗎~

如有錯誤，歡迎指出~

---

---

目錄

談?wù)勵^插、頭刪、尾插、頭插的時間復(fù)雜度

反轉(zhuǎn)一個單鏈表?

鏈表的中間結(jié)點

返回倒數(shù)第k個結(jié)點

合并兩個鏈表

---

談?wù)勵^插、頭刪、尾插、頭插的時間復(fù)雜度

頭插和頭刪的時間復(fù)雜度為O（1），

尾插和尾刪的時間復(fù)雜度為O（n） (因為尾插和尾刪要一個個遍歷完鏈表)

反轉(zhuǎn)一個單鏈表?

OJ鏈接

采用頭插法

創(chuàng)建cur指針使得cur=head.next

將head.next置空（作為尾節(jié)點）(注意要判斷head為空的情況，return head,否則會報空指針異常)

1. 創(chuàng)建curN指針使得curN=cur.next
2. 讓cur.next=head
3. head=cur

1~3步是一個循環(huán)，進(jìn)入循環(huán)條件是cur!=null（即當(dāng)cur為空時，代表cur已經(jīng)遍歷完鏈表）

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        //正常情況
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }
}

鏈表的中間結(jié)點

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

?快慢指針法

定義一個慢指針slow（每次走一步），一個快指針fast(每次走兩步)

• 即slow=slow.next
• fast=fast.next.next

這是一個循環(huán)，進(jìn)入循環(huán)的條件為fast!=null&&fast.next!=null（這兩個條件不可以交換，否則當(dāng)fast=null時，先判斷fast.next!=null時，會出現(xiàn)空指針異常）

fast!=null針對的是鏈表長度是奇數(shù)的情況

fast.next!=null針對的是鏈表長度是偶數(shù)的情況

class Solution {
    public ListNode middleNode(ListNode head) {

        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}

返回倒數(shù)第k個結(jié)點

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。OJ鏈接

?定義兩個節(jié)點fast和slow，先讓fast走k步，再讓fast和slow一起走，當(dāng)fast走完鏈表時，此時slow的位置就是倒數(shù)第k個節(jié)點。（fast和slow之間的距離就是k,當(dāng)fast走到null時，返回slow.val）

?

fast先走k步，用count計數(shù)，

• fast=fast.next
• count++

這是一個循環(huán)，條件是count<k(count是從0開始的，所以count<k 就是讓fast走了k 步)

接著讓fast和slow一起走,進(jìn)入循環(huán)條件是fast！=null

• fast=fast.next
• slow=slow.next

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode fast=head;
        ListNode slow =head;
        int count=0;
        while(count<k){
            fast=fast.next;
            count++;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
}

合并兩個鏈表

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

定義一個哨兵位節(jié)點newH,遍歷節(jié)點tmp

比較A和B鏈表的值，誰小，就將誰的節(jié)點放入新鏈表中

若A的值小( B同理)

• tmp.next=headA;
• headA=headA.next;
• tmp=tmp.next;

這是一個循環(huán)，進(jìn)入循環(huán)條件是headA!=null&&headB!=null(只要有一個鏈表遍歷完了，就跳出循環(huán))

還要判斷A走完，B還有的情況（headA=null）,（反之同理）

tmp.next=headB;

文章來源地址http://www.zghlxwxcb.cn/news/detail-859954.html

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode headH=new ListNode();
        ListNode cur=headH;
        
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){             
                cur.next=list1;
                list1=list1.next;
                cur=cur.next;        
            }
            else{
                cur.next=list2;
                list2=list2.next;
                cur=cur.next;
            }
        
        }
        if(list1==null){
            cur.next=list2;
        }
        if(list2==null){
            cur.next=list1;
        }
        return headH.next;
    }
}

到了這里，關(guān)于【Java--數(shù)據(jù)結(jié)構(gòu)】鏈表經(jīng)典OJ題詳解（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！