C++數(shù)據(jù)結(jié)構(gòu)之鏈表詳解
前言
鏈表類型的習(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)文章
c++中的內(nèi)聯(lián)函數(shù)inline用法實(shí)例
在本篇文章里小編給大家整理的是關(guān)于c++中的內(nèi)聯(lián)函數(shù)inline用法實(shí)例以及相關(guān)知識(shí)點(diǎn),有需要的朋友們學(xué)習(xí)下。2019-09-09C++中用new創(chuàng)建二維數(shù)組和指針數(shù)組實(shí)例代碼
這篇文章主要介紹了C++中用new創(chuàng)建二維數(shù)組和指針數(shù)組實(shí)例代碼,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友參考下2017-03-03