LeetCode 203.移除鏈表元素
題目：給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?和一個(gè)整數(shù)val?幌甘，請(qǐng)你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn)，并返回新的頭節(jié)點(diǎn)?痊项。
代碼：
法一：直接對(duì)原鏈表操作锅风。這種方法要考慮兩種情況：1、頭節(jié)點(diǎn)剛好是要?jiǎng)h除的點(diǎn)鞍泉；2遏弱、非頭節(jié)點(diǎn)是要?jiǎng)h除的點(diǎn)。第一種情況通過(guò)head=head->next實(shí)現(xiàn)頭節(jié)點(diǎn)的移動(dòng)塞弊，第二種情況就是正常的刪除節(jié)點(diǎn)的操作漱逸。有一種特殊情況需要考慮到：例如刪除的元素是1泪姨，但是鏈表里面全是1，這時(shí)候頭節(jié)點(diǎn)應(yīng)該不斷地向后移動(dòng)饰抒，直至為空肮砾，所以第一種情況的代碼中應(yīng)該用while而不是if。此外在寫代碼時(shí)要注意袋坑，我們不能對(duì)空指針進(jìn)行操作仗处，所以在對(duì)進(jìn)入循環(huán)時(shí)要判斷空節(jié)點(diǎn)的情況。
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* removeElements(ListNode* head, int val) {
? ? while(head!=NULL&&head->val==val)
? ? {
? ? ? ? ListNode* temp=head;
? ? ? ? head=head->next;
? ? ? ? delete temp;
? ? }
? ? ListNode* p=head;
? ? while(p!=NULL&&p->next!=NULL)
? ? {
? ? ? ? if(p->next->val==val)
? ? ? ? {
? ? ? ? ? ? ListNode* temp=p->next;
? ? ? ? ? ? p->next=temp->next;
? ? ? ? ? ? delete temp;
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? p=p->next;
? ? ? ? }
? ? }
? ? return head;
? ? }
};
法二：構(gòu)造虛擬頭節(jié)點(diǎn)枣宫。這種方法是在頭節(jié)點(diǎn)之前再加上一個(gè)節(jié)點(diǎn)婆誓，把頭節(jié)點(diǎn)變成一個(gè)中間的節(jié)點(diǎn)，避免了法一的分類判斷也颤，這樣代碼更加簡(jiǎn)潔洋幻。需要注意的是，最后返回的指針是vhead->next翅娶，因?yàn)樵瓉?lái)的head可能被刪除了文留，而虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)永遠(yuǎn)都是原鏈表的頭節(jié)點(diǎn)。
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* removeElements(ListNode* head, int val) {
? ? ListNode *vhead=new ListNode(0);
? ? vhead->next=head;
? ? ListNode *p=vhead;
? ? while(p!=NULL&&p->next!=NULL)
? ? {
? ? ? ? if(p->next->val==val)
? ? ? ? {
? ? ? ? ? ? ListNode* temp=p->next;
? ? ? ? ? ? p->next=temp->next;
? ? ? ? ? ? delete temp;
? ? ? ? }else{
? ? ? ? ? ? p=p->next;
? ? ? ? }
? ? }
? ? return vhead->next;
? ? }
};
LeetCode 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)的值。如果索引無(wú)效它浅，則返回-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)。
代碼：
class MyLinkedList {
public:
struct LinkNode{
? ? ? ? int val;
? ? ? ? LinkNode* next;
? ? ? ? LinkNode(int val):val(val),next(NULL){}
? ? };
? ? MyLinkedList() {
? ? vhead=new LinkNode(0);
? ? size=0;
? ? }
? ? int get(int index) {
? ? ? if (index > (size - 1) || index < 0) {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? LinkNode* cur =vhead->next;
? ? ? ? while(index--){
? ? ? ? ? ? cur = cur->next;
? ? ? ? }
? ? ? ? ? ? return cur->val;
? ? }
? ? void addAtHead(int val) {
? ? LinkNode* p=new LinkNode(val);
? ? p->next=vhead->next;
? ? vhead->next=p;
? ? size++;
? ? }
? ? void addAtTail(int val) {
? ? LinkNode* last=new LinkNode(val);
? ? LinkNode* p=vhead;
? ? while(p->next!=NULL)
? ? {
? ? ? ? p=p->next;
? ? }
? ? p->next=last;
? ? size++;
? ? }
? ? void addAtIndex(int index, int val) {
? ? ? ? if(index>size) return ;
? ? ? ? if(index<0) index=0;
? ? ? ? LinkNode *newnode=new LinkNode(val);
? ? ? ? LinkNode* p=vhead;
? ? ? ? while(index--)
? ? ? ? {
? ? ? ? ? ? p=p->next;
? ? ? ? }
? ? ? ? newnode->next=p->next;
? ? ? ? p->next=newnode;
? ? ? ? size++;
? ? }
? ? void deleteAtIndex(int index) {
? ? if(index>=size||index<0)
? ? {
? ? ? ? return ;
? ? }
? ? ? ? LinkNode* p=vhead;
? ? ? ? LinkNode* temp=p;
? ? ? ? while(index)
? ? ? ? {
? ? ? ? ? ? p=p->next;
? ? ? ? ? ? index--;
? ? ? ? }
? ? ? ? temp=p->next;
? ? ? ? p->next=temp->next;
? ? ? ? delete temp;
? ? ? ? size--;
? ? }
private:
? ? int size;
? ? LinkNode *vhead;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
注意：
1升熊、本題在頭節(jié)點(diǎn)節(jié)點(diǎn)之前加入了虛擬頭節(jié)點(diǎn)vhead俄烁，這樣在鏈表中任意一處的添加或者刪除操作都能夠保持一致性，代碼邏輯也更加簡(jiǎn)介级野。
2页屠、在刪除、添加的時(shí)候蓖柔，因?yàn)閱捂湵頍o(wú)法找到前面節(jié)點(diǎn)的特性辰企，所以每個(gè)要操作的位置是p->next，也就是需要操作的前一個(gè)位置才是p况鸣。同時(shí)牢贸，為了避免出錯(cuò)，可以找一個(gè)極端的例子帶入懒闷，比如index=0時(shí)十减，這樣寫循環(huán)條件時(shí)就不容易出錯(cuò)。
LeetCode 206.反轉(zhuǎn)鏈表
題目：給你單鏈表的頭節(jié)點(diǎn)?head愤估，請(qǐng)你反轉(zhuǎn)鏈表帮辟，并返回反轉(zhuǎn)后的鏈表。
代碼：
法一：雙指針?lè)ㄍ嫜妗６x一組指針由驹，開(kāi)始時(shí)cur指向head，pre指向head的前一個(gè)元素昔园，因?yàn)榉崔D(zhuǎn)后原本的head會(huì)指向NULL蔓榄，所以pre最開(kāi)始指向NULL。之后cur->next會(huì)指向pre實(shí)現(xiàn)反轉(zhuǎn)默刚，然后pre甥郑、cur同時(shí)向后移動(dòng)一位，繼續(xù)上述操作荤西。注意：因?yàn)閏ur->next=pre時(shí)原來(lái)cur的下一個(gè)節(jié)點(diǎn)就斷開(kāi)了澜搅，為了保證連續(xù)性，所以在cur指向pre之前邪锌，應(yīng)該用一個(gè)臨時(shí)節(jié)點(diǎn)存著原來(lái)cur的下一個(gè)節(jié)點(diǎn)勉躺。
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* reverseList(ListNode* head) {
? ? ListNode* cur=head;
? ? ListNode* temp=head;
? ? ListNode* pre=NULL;
? ? while(cur!=NULL)
? ? {
? ? ? ? temp=cur->next;
? ? ? ? cur->next=pre;
? ? ? ? pre=cur;
? ? ? ? cur=temp;? ?
? ? }
? ? return pre;
? ? }
};
法二：遞歸法。這種方法本質(zhì)和雙指針是一樣的觅丰，只不過(guò)將雙指針的while函數(shù)寫成了遞歸的方式饵溅。
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* reverse(ListNode* pre,ListNode* cur)
? ? {
? ? if(cur==NULL) return pre;
? ? ListNode* temp=cur->next;
? ? cur->next=pre;
? ? return reverse(cur,temp);
? ? }
? ? ListNode* reverseList(ListNode* head) {
? ? return reverse(NULL,head);
? ? }
};
