LeetCode 203.移除鏈表元素
題目：給你一個鏈表的頭節(jié)點?head?和一個整數(shù)val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點，并返回新的頭節(jié)點?。
代碼：
法一：直接對原鏈表操作。這種方法要考慮兩種情況：1、頭節(jié)點剛好是要刪除的點；2、非頭節(jié)點是要刪除的點。第一種情況通過head=head->next實現(xiàn)頭節(jié)點的移動，第二種情況就是正常的刪除節(jié)點的操作。有一種特殊情況需要考慮到：例如刪除的元素是1，但是鏈表里面全是1，這時候頭節(jié)點應該不斷地向后移動，直至為空，所以第一種情況的代碼中應該用while而不是if。此外在寫代碼時要注意，我們不能對空指針進行操作，所以在對進入循環(huán)時要判斷空節(jié)點的情況。
/**
* 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;
? ? }
};
法二：構造虛擬頭節(jié)點。這種方法是在頭節(jié)點之前再加上一個節(jié)點，把頭節(jié)點變成一個中間的節(jié)點，避免了法一的分類判斷，這樣代碼更加簡潔。需要注意的是，最后返回的指針是vhead->next，因為原來的head可能被刪除了，而虛擬頭節(jié)點的下一個節(jié)點永遠都是原鏈表的頭節(jié)點。
/**
* 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.設計鏈表
題目：設計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應該具有兩個屬性：val和next。val是當前節(jié)點的值，next是指向下一個節(jié)點的指針/引用。如果要使用雙向鏈表，則還需要一個屬性prev以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(jié)點都是 0-index 的。
在鏈表類中實現(xiàn)這些功能：get(index)：獲取鏈表中第index個節(jié)點的值。如果索引無效，則返回-1。addAtHead(val)：在鏈表的第一個元素之前添加一個值為val的節(jié)點。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。addAtTail(val)：將值為val?的節(jié)點追加到鏈表的最后一個元素。addAtIndex(index,val)：在鏈表中的第index個節(jié)點之前添加值為val的節(jié)點。如果index等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果?index?大于鏈表長度，則不會插入節(jié)點。如果index小于0，則在頭部插入節(jié)點。deleteAtIndex(index)：如果索引index?有效，則刪除鏈表中的第index?個節(jié)點。
代碼：
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é)點節(jié)點之前加入了虛擬頭節(jié)點vhead，這樣在鏈表中任意一處的添加或者刪除操作都能夠保持一致性，代碼邏輯也更加簡介。
2、在刪除、添加的時候，因為單鏈表無法找到前面節(jié)點的特性，所以每個要操作的位置是p->next，也就是需要操作的前一個位置才是p。同時，為了避免出錯，可以找一個極端的例子帶入，比如index=0時，這樣寫循環(huán)條件時就不容易出錯。
LeetCode 206.反轉(zhuǎn)鏈表
題目：給你單鏈表的頭節(jié)點?head，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
代碼：
法一：雙指針法。定義一組指針，開始時cur指向head，pre指向head的前一個元素，因為反轉(zhuǎn)后原本的head會指向NULL，所以pre最開始指向NULL。之后cur->next會指向pre實現(xiàn)反轉(zhuǎn)，然后pre、cur同時向后移動一位，繼續(xù)上述操作。注意：因為cur->next=pre時原來cur的下一個節(jié)點就斷開了，為了保證連續(xù)性，所以在cur指向pre之前，應該用一個臨時節(jié)點存著原來cur的下一個節(jié)點。
/**
* 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ì)和雙指針是一樣的，只不過將雙指針的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);
? ? }
};
