欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++數(shù)據(jù)結(jié)構(gòu)之鏈表詳解

 更新時(shí)間：2021年08月16日 11:08:17   作者：caiyec  
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之鏈表的創(chuàng)建的相關(guān)資料,希望通過本文幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下

前言

鏈表類型的習(xí)題常用的技巧就是定義指針來代替head的，替head走，要么就是數(shù)學(xué)問題，環(huán)形鏈表就是利用數(shù)學(xué)思想取解決的，要么就是定義雙指針來操作鏈表。

一、刪除鏈表中給定值為key的節(jié)點(diǎn)

定義兩個(gè)變量，一個(gè)使待刪除的節(jié)點(diǎn)，一個(gè)為待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，最后記得判斷頭節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)，最后返回頭節(jié)點(diǎn)。

 public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }

二、反轉(zhuǎn)鏈表

定義雙指針法，類似于頭插法，來將鏈表的節(jié)點(diǎn)頭插法

cur節(jié)點(diǎn)是待反轉(zhuǎn)的節(jié)點(diǎn) curNext是保存下一個(gè)節(jié)點(diǎn)的地址值

1.先保存待反轉(zhuǎn)節(jié)點(diǎn)下一個(gè)地址值，之后將頭節(jié)點(diǎn)的next置空

2.只有用頭插法將節(jié)點(diǎn)頭插即可。

public ListNode reverseList(ListNode head) {
        //三指針法來反轉(zhuǎn)鏈表
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur=head;//要頭插的節(jié)點(diǎn)
        ListNode curNext=head.next;//保存下一個(gè)節(jié)點(diǎn)的地址值
        cur=curNext;
        head.next=null;
        while(cur!=null){
            curNext=curNext.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }

三、返回鏈表的中間節(jié)點(diǎn)

定義快慢指針，注意偶數(shù)節(jié)點(diǎn)和奇數(shù)節(jié)點(diǎn)的情況

注意判斷條件 在偶數(shù)情況下 如果是判斷fast.next.next就會(huì)空指針異常，必須把判斷條件兩個(gè)都加上。

public ListNode middleNode(ListNode head) {
        //定義快慢指針 快指針比慢指針多走一步   注意奇數(shù)和偶數(shù)情況
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

四、刪除鏈表的倒數(shù)第K個(gè)節(jié)點(diǎn)

定義快慢指針 快指針先走n-1步 之后慢指針再走,修改地址值即可

public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode dummy=new ListNode(0,head);
        ListNode slow=dummy;
        for(int i=1;i<n;i++){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }

五、分割鏈表

給定X值，分割鏈表 前面鏈表為小于X的值，后面鏈表為大于等于X的值
要考慮很多情況

1.第一次插入鏈表時(shí) 要將頭節(jié)點(diǎn)和尾巴節(jié)點(diǎn)都指向插入的節(jié)點(diǎn)

2.不是第一次插入時(shí)，只需要把尾巴節(jié)點(diǎn)next值指向插入的節(jié)點(diǎn)，之后把尾巴節(jié)點(diǎn)往后挪

3.如果前面鏈表為空，返回后面鏈表的頭

4。還需要將后面節(jié)點(diǎn)的next值置空，之后連接兩個(gè)鏈表。

 public ListNode partition(ListNode head, int x) {
        //分割鏈表 將小于x的分為一部分，將大于等于x的分為一部分呢！ 乖乖yy
        if(head==null){
            return null;
        }
        ListNode xh=null;//小于x的頭節(jié)點(diǎn)
        ListNode xe=null;;//小于x的尾巴節(jié)點(diǎn)
        ListNode Xh=null;//大于等于X的頭節(jié)點(diǎn)
        ListNode Xe=null;//大于等于X的尾節(jié)點(diǎn)
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                //小于X的部分
                if(xh==null){
                    //第一次插入
                    xh=cur;
                    xe=cur;
                }else{
                    //不是第一次插入
                    xe.next=cur;
                    xe=cur;
                }
            }else{
                //>=X 的部分
                if(Xh==null){
                    //第一次插入
                    Xh=cur;
                    Xe=cur;
                }else{
                    //不是第一次插入
                    Xe.next=cur;
                    Xe=cur;
                }
            }
            cur=cur.next;
        }//判斷 所有元素都大于x 前面的鏈表沒有數(shù)據(jù) 要返回后面的鏈表
         if(xh==null){
            return Xh;
        }
        xe.next=Xh;
        if(Xh!=null){
            //將最后一個(gè)元素置為null
            Xe.next=null;
        }
        return xh;
    }

六、合并兩個(gè)有序鏈表

和合并有序數(shù)組是一樣的，鏈表復(fù)雜一些要將后面節(jié)點(diǎn)地址先保存，之后定義傀儡節(jié)點(diǎn)，按照值小的順序連接起來

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //1.思路就是先定傀儡節(jié)點(diǎn)，將鏈表穿起來 定義兩個(gè)變量將后面地址保存起來 之后串糖葫蘆一樣串起來
    ListNode dummy=new ListNode(-1);
    ListNode head=dummy;//保存傀儡節(jié)點(diǎn)
    ListNode cur1=l1;//保存節(jié)點(diǎn)后面的地址值
    ListNode cur2=l2;
    while(l1!=null&&l2!=null){
        cur1=l1.next;
        cur2=l2.next;
        if(l1.val<=l2.val){
            dummy.next=l1;
            l1=cur1;
        }else{
            dummy.next=l2;
            l2=cur2;
        }
        dummy=dummy.next;
    }
    if(l1!=null){
        dummy.next=l1;
    }
    if(l2!=null){
        dummy.next=l2;
    }
    return head.next;
    }

七、刪除有序鏈表中重復(fù)節(jié)點(diǎn)

雙指針 遇到相等的就跳過 ，最后要將最后一個(gè)節(jié)點(diǎn)置為空。

 public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(prev.val==cur.val){
                cur=cur.next;
            }else{
                prev.next=cur;
                prev=cur;
                cur=cur.next;
            }
        }
        prev.next=cur;
        return head;
    }

八、環(huán)形鏈表

先用set判斷是否存在 空間復(fù)雜度為O（N），不太符合題目要求

public boolean hasCycle(ListNode head) {
       HashSet<ListNode> set=new HashSet<>();
       while(head!=null){
           set.add(head);
           head=head.next;
           if(set.contains(head)){
               return true;
           }
       }
       return false;
    }

2.快慢指針數(shù)學(xué)問題，快指針走兩步，慢指針走一步，有環(huán)一定相遇，沒有環(huán)就不會(huì)相遇 空間復(fù)雜度為O(1)

 public boolean hasCycle(ListNode head) {
      //快慢指針還是數(shù)學(xué)問題
      if(head==null||head.next==null){
          return false;
      }  
      ListNode slow=head;
      ListNode fast=head.next;
      while(slow!=fast){
          if(fast==null||fast.next==null){
              return false;
          }
          fast=fast.next.next;
          slow=slow.next;
      }
      return true;
    }

九、相交鏈表

1.先利用set存儲(chǔ)節(jié)點(diǎn) 之后循環(huán)判斷，空間復(fù)雜度為O（N）時(shí)間復(fù)雜度為O（N），比較慢

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode>set=new HashSet<>();
        while(headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while(headB!=null){
            if(set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
    }

2.雙指針，確實(shí)沒想出來，看了題解才知道是兩個(gè)鏈表相連接，遍歷是否有想交的節(jié)點(diǎn)

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode cur1=headA;
      ListNode cur2=headB;
      while(cur1!=cur2){
        cur1=cur1==null?headB:cur1.next;
        cur2=cur2==null?headA:cur2.next;
      }
       return cur1;
    }

十、兩數(shù)相加

這道題沒什么技巧，就是注意很多特殊情況，加完要判斷進(jìn)位，我第一次敲的時(shí)候能執(zhí)行但是不能過，沒有考慮到特殊情況。
最后看評(píng)論解答就是用一個(gè)進(jìn)位標(biāo)志數(shù)來解決，學(xué)到了。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list=new ListNode(-1);
        ListNode head=list;
        int t=0;
        while(l1!=null||l2!=null||t!=0){
            if(l1!=null){
                t+=l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                t+=l2.val;
                l2=l2.next;
            }
            list.next=new ListNode(t%10);
            list=list.next;
            t/=10;
        }
        return head.next;
    }

十一、回文鏈表

1.可以將鏈表中值存放在順序表中，之后定義雙指針遍歷判斷

2.快慢指針帶反轉(zhuǎn)

3.利用棧實(shí)現(xiàn)li

public boolean isPalindrome(ListNode head) {
        //利用棧來實(shí)現(xiàn)回文結(jié)構(gòu)
        Stack<Integer> stack=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur.val);
            cur=cur.next;
        }
        ListNode cur1=head;
        while(cur1!=null){
            if(cur1.val!=stack.pop()){
                return false;
            }
            cur1=cur1.next;
        }
        return true;
    }

定義快慢指針，之后反轉(zhuǎn)鏈表來實(shí)現(xiàn)

public boolean isPalindrome(ListNode head) {
        //快慢指針來反轉(zhuǎn)鏈表
        if(head==null||head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //走到中間節(jié)點(diǎn)，反轉(zhuǎn)鏈表
        slow=reverse(slow.next);
        while(slow!=null){
            if(head.val!=slow.val){
                return false;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        //反轉(zhuǎn)鏈表
        ListNode cur=head;
        ListNode curNext=head.next;
        cur=curNext;
        head.next=null;
        while(cur!=null){
            curNext=curNext.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }

在這里插入圖片描述

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望你能給多多關(guān)注腳本之家的更多內(nèi)容！

相關(guān)文章

最新評(píng)論