代碼隨想錄：鏈表
鏈表是一種通過指針串聯(lián)在一起的線性結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)由兩部分組成，數(shù)據(jù)域（存數(shù)據(jù)）和指針域（存指向下一個(gè)節(jié)點(diǎn)的指針），最后一個(gè)節(jié)點(diǎn)指針域指向NULL。鏈表的入口叫頭節(jié)點(diǎn)head
單鏈表：節(jié)點(diǎn)只能指向下一個(gè)節(jié)點(diǎn)next? A->C->D->E->NULL
雙鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向下一個(gè)節(jié)點(diǎn)一個(gè)指向上一個(gè)節(jié)點(diǎn)，即可以向前查詢也可以向后查詢? NULL<-A<=>C<=>D<=>E->NULL
循環(huán)鏈表：首尾相連?
鏈表的存儲(chǔ)方式，鏈表在內(nèi)存中是不連續(xù)分布的，鏈表通過指針域的指針連接內(nèi)存中各個(gè)節(jié)點(diǎn)
鏈表的定義：
public?class?ListNode?{
?? ? ?public?int?val;
?? ? ?public?ListNode?next;
?? ? ?public?ListNode(int?val=0,?ListNode?next=null)?{
?? ? ? ? ?this.val?=?val;
??????????this.next?=?next;
? ? ? ? }
}
鏈表的操作：A->C->D->E->NULL刪除節(jié)點(diǎn)D，將C的next指向E即可
A->C->D->E->NULL將F添加到CD中間，C的next指向F，F(xiàn)的next指向E
鏈表的長(zhǎng)度是可以不固定的，適合頻繁增加刪除較少查詢的情況
判斷鏈表是否有環(huán)可用雙指針，分別定義fast和slow指針，fast每次移動(dòng)兩步slow每次移動(dòng)一步，若有環(huán)則二者一定會(huì)在環(huán)中相遇（都進(jìn)入環(huán)中后二者相對(duì)距離每次移動(dòng)改變量為1因此一定可以相遇）
尋找環(huán)的入口：假設(shè)從頭到環(huán)入口節(jié)點(diǎn)數(shù)x，入口到相遇點(diǎn)節(jié)點(diǎn)數(shù)為y，相遇點(diǎn)到環(huán)入口節(jié)點(diǎn)數(shù)為z，二者相遇時(shí)slow指針移動(dòng)節(jié)點(diǎn)數(shù)為x+y，fast指針移動(dòng)節(jié)點(diǎn)數(shù)為x+y+n(y+z)，n為在環(huán)內(nèi)移動(dòng)的圈數(shù)。由于fast一次移動(dòng)兩步，slow一次移動(dòng)一步，因此可得等式2(x+y)=x+y+n(y+z)，化簡(jiǎn)后為x+y=n(y+z)，x=(n-1)(y+z)+z。當(dāng)n=1時(shí)，有x=z，此時(shí)令一個(gè)指針從頭結(jié)點(diǎn)出發(fā)，另一個(gè)指針從相遇點(diǎn)出發(fā)，每次都只移動(dòng)一步則二者相遇點(diǎn)就是環(huán)的入口，n不為1時(shí)相遇前環(huán)內(nèi)的指針額外走n-1個(gè)環(huán)的距離，最終相遇點(diǎn)不會(huì)改變。
力扣203：移除鏈表元素
public?class?Solution?{
????public?ListNode?RemoveElements(ListNode?head,?int?val)?{
????????ListNode?dummy=new?ListNode(0);
????????dummy.next=head;
????????ListNode?cur=dummy;
//建立虛擬頭節(jié)點(diǎn)，將后續(xù)操作統(tǒng)一，否則需要特殊處理頭節(jié)點(diǎn)
????????while(cur.next!=null){
????????????if(cur.next.val==val){
????????????????cur.next=cur.next.next;
//刪除操作，指針指向下個(gè)指針指向的節(jié)點(diǎn)
????????????}
????????????else{
????????????????cur=cur.next;
????????????}
????????}
????????return?dummy.next;
//返回的時(shí)候去掉虛擬頭節(jié)點(diǎn)
????}
}
力扣707：設(shè)計(jì)鏈表
設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。
在鏈表類中實(shí)現(xiàn)這些功能：
get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val? 的節(jié)點(diǎn)。如果 index 等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長(zhǎng)度，則不會(huì)插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/design-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
?public?class?LinkedNode{
????????public?int?val;
????????public?LinkedNode?next;
????????public?LinkedNode(int?val){
????????????this.val=val;
????????????this.next=next;
????????}
????}//定義鏈表結(jié)構(gòu)體
public?class?MyLinkedList?{
????public?int?size;
????public?LinkedNode?head;
????public?MyLinkedList()?{
????????size=0;
????????head=new?LinkedNode(0);
//初始化鏈表
????}
????
????
????public?int?Get(int?index)?{
????????if(index>(size-1)||index<0){
????????????return?-1;
//查不到的元素返回-1
????????}
????????LinkedNode?cur=head;
????????while(index-->=0){
????????????cur=cur.next;
//因?yàn)橛刑摂M頭節(jié)點(diǎn)要多循環(huán)一次才是真正的位置
????????}
????????return?cur.val;
????}
????
????public?void?AddAtHead(int?val)?{
????????AddAtIndex(0,val);
????}
????
????public?void?AddAtTail(int?val)?{
????????AddAtIndex(size,val);
????}
????
????public?void?AddAtIndex(int?index,?int?val)?{
???????if(index>size){
???????????return;
//index=size就是加在末尾后面的空位，加上虛擬頭節(jié)點(diǎn)鏈表長(zhǎng)度實(shí)際為size+1
???????}
????????LinkedNode?cur=head;
????????LinkedNode?temp=new?LinkedNode(val);
????????while(index-->0){
????????????cur=cur.next;
????????}
????????temp.next=cur.next;
????????cur.next=temp;
????????size++;
????}
????
????public?void?DeleteAtIndex(int?index)?{
????????if(index>=size||index<0){
????????????return;
//index=size時(shí)末尾為空無法刪除
????????}
????????LinkedNode?cur=head;
????????while(index-->0){
????????????cur=cur.next;
????????}
????????cur.next=cur.next.next;
????????size--;
????}
}
力扣206：反轉(zhuǎn)鏈表
//雙指針法，cur指向頭節(jié)點(diǎn)，pre作為新鏈表的頭節(jié)點(diǎn)，temp保存cur.next在執(zhí)行完將cur.next指向pre后將pre指向cur，cur指向temp，以此完成cur和pre的移動(dòng)
public?class?Solution?{
????public?ListNode?ReverseList(ListNode?head)?{
????????ListNode?cur=head;
????????ListNode?pre=null;
????????ListNode?temp;
????????while(cur!=?null){
????????????temp=cur.next;
????????????cur.next=pre;
????????????pre=cur;
????????????cur=temp;
????????}
????????return?pre;
????}
}
//遞歸法
public?class?Solution?{
????public?ListNode?ReverseList(ListNode?head)?{
????????return?Reverse(null,head);
????}
????public?ListNode?Reverse(ListNode?pre,ListNode?cur){
//定義反轉(zhuǎn)操作將cur.next指向pre
????????if(cur==null){
????????????return?pre;
//結(jié)束條件，返回反轉(zhuǎn)后的鏈表
????????}
????????ListNode?temp=cur.next;
????????cur.next=pre;
????????return?Reverse(cur,temp);//使用遞歸進(jìn)行循環(huán)
????}
}
力扣19：刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)
public?class?Solution?{
????public?ListNode?RemoveNthFromEnd(ListNode?head,?int?n)?{
????????ListNode?nHead=new?ListNode(0);
????????nHead.next=head;
//虛擬頭節(jié)點(diǎn)，這樣做就不需要討論刪除頭結(jié)點(diǎn)的特殊情況
????????ListNode?left=nHead;
????????ListNode?right=nHead;
//雙指針
????????while(n>=0)
????????{
????????????right=right.next;
????????????n--;
//快指針先走出n+1步
????????}
????????while(right!=null)
????????{
????????????left=left.next;
????????????right=right.next;
//同時(shí)移動(dòng)快慢指針，這樣當(dāng)快指針指向null時(shí)慢指針恰好指在倒數(shù)第n+1個(gè)元素
????????}
????????left.next=left.next.next;
//刪除慢指針指向的下一個(gè)元素
????????return?nHead.next;
//有虛擬頭節(jié)點(diǎn)因此在此處返回值中應(yīng)刪除該虛擬頭節(jié)點(diǎn)
????}
}
力扣142：環(huán)形鏈表II
public?class?Solution?{
????public?ListNode?DetectCycle(ListNode?head)?{
????????ListNode?slow=head;
????????ListNode?fast=head;
????????while(fast!=null&&fast.next!=null){
????????????slow=slow.next;
????????????fast=fast.next.next;
//判斷有沒有環(huán)
????????????if(slow==fast){
????????????ListNode?n1=fast;
????????????ListNode?n2=head;
????????????while(n1!=n2){
????????????????n1=n1.next;
????????????????n2=n2.next;
//成環(huán)了就從頭和相遇點(diǎn)開始一步步找新的相遇點(diǎn)即為環(huán)入口
????????????}
????????????return?n2;
????????}
????????}
????????
????????return?null;
//沒成環(huán)返回null
????}
}
//（代碼第一次寫完超時(shí)了，寫的判斷入口的部分沒有放到循環(huán)內(nèi)所以出現(xiàn)死循環(huán)）
