目

1.常用技巧

1.1.畫圖

?1.2.添加虛擬頭節點

?1.3.大膽引入中間變量

1.4.快慢雙指針

1.4.1判斷鏈表是否有環

?1.4.2找鏈表中環的入口

?2.常用操作

2.1. 創建一個新節點

2.2.尾插

2.3.頭插?

---

1.常用技巧

1.1.畫圖

畫圖可以讓一些抽象的文字語言更加形象生動

畫圖！！！->直觀+形象+便于我們理解

例如：

現在有一個結構體

struct s
{struct s*pprev;struct s*pnext;
}

?他們的的關系如下：

prev->pnext->pnext=cur;
cur->pprev->prev=prev;
cur->pnext=prev;
prev->pprev=cur;

是不是感覺無從下手，但是我們只要轉化為圖形就能很好的理解：?

?1.2.添加虛擬頭節點

?在鏈表算法題中很多時候都會給我們傳來的頭節點為空情況，如果我們沒有判斷直接對空指針進行解引用，程序可能會直接崩潰：?

如果我們能引入一個頭節點，則可以避免直接對空指針解引用情況

這個頭節點我們也會稱作‘哨兵位’：?

?1.3.大膽引入中間變量

?如果不引入中間變量

prev->pnext->pprev=cur;
cur->pnext=prev->pnext;
prev->pnext=cur;
cur->pprev=prev;

?引入中間變量next,代碼更加干凈整潔

next=prev->pnext;
next->pprev=cur;
cur->pnext=next;
prev->pnext=cur;
cur->pprev=prev;

1.4.快慢雙指針

1.4.1判斷鏈表是否有環

• 快指針（fast）一次走兩步，慢指針（slow）一次走兩步
• 對有環的鏈表來說，慢指針相當于快指針不動，快指針相對慢指針一次一步
• 對無環的鏈表來說，快指針會提前走出鏈表，讓循環結束
• 循環條件（fast==slow）有環，（fast->next==nullptr||fast->next->next==nullptr）無環

?相遇：

?1.4.2找鏈表中環的入口

• 假設鏈表共有a+b個元素，從head（頭節點）到圓環入口有a個元素，圓環有b個元素
• 在有環基礎上，兩者相遇，快指針和慢指針分別走了f，s。f=2s(因為快指針是慢指針速度的兩倍)
• f=s+nb（fast比slow多走了n個圓環），所以f=2nb,s=nb
  • 固定此時相遇位置，slow從頭開始再走一遍，slow到fast的位置就是圓環b的長度
  • 不固定此時相遇位置，slow從頭出發，fast從相遇位置出發，兩者都每次走一步，兩者再次相遇的位置即為圓環入口的位置?

2.常用操作

2.1. 創建一個新節點

例如：創建一個head的指針

s*head=new s();

2.2.尾插

tail->next=cur;
cur=tail;

2.3.頭插?

cur->next=head->next;
head->next=cur;

常用于反轉鏈表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* phead=new ListNode();if(head==nullptr) return nullptr;phead->next=head;ListNode*cur=head->next;head->next=nullptr;while(cur!=nullptr){ListNode*temp=cur->next;cur->next=phead->next;phead->next=cur;cur=temp;}return phead->next;}
};

?

?

?