Java中鏈表題有哪些

這篇文章主要介紹了Java中鏈表題有哪些，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

第一題 移除鏈表元素

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val ，請(qǐng)你刪除鏈表中所有滿(mǎn)足 Node.val == val 的節(jié)點(diǎn)，并返回 新的頭節(jié)點(diǎn) 。

輸入：head = [1,2,6,3,4,5,6], val = 6

輸出：[1,2,3,4,5]

這道題還是比較簡(jiǎn)單的我們需要讓刪除的節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后一個(gè)就行。就比如cur.next==cur.next.next;。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode header=new ListNode(-1);
        header.next=head;
        ListNode cur =header;
        while(cur.next!=null){
            if(cur.next.val==val){
                 cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
return header.next;
    }
}

第二題 反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

輸入：head = [1,2,3,4,5]

輸出：[5,4,3,2,1]

這也是一個(gè)簡(jiǎn)單題，我們還是先弄一個(gè)尾結(jié)點(diǎn)，因?yàn)殒湵淼淖詈笠粋€(gè)結(jié)點(diǎn)的下一個(gè)是一個(gè)null，這道題我們可以通過(guò)一次循環(huán)讓后一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre =null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
      
return pre;
    }
}

第三題 鏈表的中心結(jié)點(diǎn)

給定一個(gè)頭結(jié)點(diǎn)為 head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

答：這個(gè)也是一個(gè)簡(jiǎn)單題我們需要用到快慢指針，當(dāng)快指針指完之后，慢的結(jié)點(diǎn)肯定是中點(diǎn)比如18 快的可以走9步每次走兩步走到18，慢的可以每次走一部走9步。剛好到中點(diǎn)。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p =head;
        ListNode q =head;
        while(q!=null&&q.next!=null){
            q=q.next.next;
            p=p.next;
        }
return p;

    }
}

第四題 倒數(shù)第k個(gè)結(jié)點(diǎn)

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

輸入：

1,{1,2,3,4,5}

復(fù)制

返回值：

{5}

答：這道題也是一個(gè)簡(jiǎn)單題，直接簡(jiǎn)單粗暴的搞出來(lái)倒數(shù)第k個(gè)點(diǎn)的值就行；

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

這道題寫(xiě)的有點(diǎn)麻煩了，我們也可以用快慢指針做。一個(gè)指針走5步一個(gè)走4步。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p=head;
        ListNode q=head;
       for(int i = 0; i < k; i++) {
           if (p != null) {
            p= p.next;
        } else {
            return null;
        }
    }
        while(p!=null){
            p=p.next;
            q=q.next;
        }
        return q;
    }
}

第五題 合并兩個(gè)有序鏈表

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

輸入：l1 = [1,2,4], l2 = [1,3,4]

輸出：[1,1,2,3,4,4]

答：這道題考到了怎么將兩個(gè)鏈表合并，我們需要將兩個(gè)鏈表從大到小合并起來(lái)。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 任一為空，直接連接另一條鏈表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }
}

第六題 鏈表分割

現(xiàn)有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫(xiě)一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變?cè)瓉?lái)的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。

輸入：l1 = [1,2，1,3,2] 3

輸出：[1，2，1，2，3]

這道題比較難了需要我們創(chuàng)建兩個(gè)鏈表，一個(gè)數(shù)大與等于x的鏈表，另一個(gè)數(shù)小于x的鏈表。然后讓上一個(gè)鏈表的下一個(gè)尾結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)的尾巴結(jié)點(diǎn)。

這里我們需要用到如何將兩個(gè)鏈表合并成一個(gè)鏈表。

做題的時(shí)候先想怎么做然后在動(dòng)手！

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode newHead = new ListNode(0);
        ListNode flagHead = new ListNode(0);
        ListNode newh = newHead;
        ListNode flagh = flagHead;
        while(pHead != null){
            if(pHead.val < x){
                newh.next = new ListNode(pHead.val);
                newh = newh.next;
            }else{
                flagh.next = new ListNode(pHead.val);
                flagh = flagh.next;
            }
            pHead = pHead.next;
        }
        newh.next = flagHead.next;
        return newHead.next;
    }
}

第七題 判斷是否回文

對(duì)于一個(gè)鏈表，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。

給定一個(gè)鏈表的頭指針A，請(qǐng)返回一個(gè)bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長(zhǎng)度小于等于900。

1->2->2->1

返回：true

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here 
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
         ListNode cur=slow.next；
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //3.一個(gè)從前往后，一個(gè)從后往前  如果相遇，則證明回文
        while(head!=slow){
            if(head.val!=slow.val){//先判斷值是否相等
                return false;
            }
            if(head.next==slow){//偶數(shù)情況下
                return true;
            }
            head=head.next;
            slow=slow.next;
    }
        return true;    
}

第八題 相交鏈表

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null 。

可以用笨方法就是計(jì)算出來(lái)每個(gè)鏈表的個(gè)數(shù)然后讓多的先走。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
                ListNode last = headB;
        while (last.next != null) {
            last = last.next;
        }
last.next = headB;

        ListNode fast = headA;
        ListNode slow = headA;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = headA;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                last.next = null;
                return fast;
            }
        }
        last.next = null;
        return null;
    }
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java中鏈表題有哪些”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!