Leetcode 203. Remove Linked List Elements

2019-11-09 21:03:46

字體：大中小

來源：轉載

供稿：網友

Remove all elements from a linked list of integers that have value val.

Example Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5

s思路： 1. 操作鏈表，要刪除數。首先想想鏈表的邊界是什么？左邊是頭節點，是邊界，右邊是為節點也是邊界。如果要刪除的節點恰好是頭節點，就要考慮頭指針改變的問題。因此用dummy或pointer-to-pointer。 2. 用dummy：首先需要新建一個node,賦初值為0,然后需要一個dummy指針指向這個node。 3. 用pointer-to-pointer: 之前總結過指向指針的指針的兩種操作：第一種是只移動指向指針的指針到新的位置，這個操作相當于站位，放到需要的地方，不對鏈表產生改變；第二種操作是修改被指針指向的指針里的地址，讓指針指向新的節點，這個操作會修改鏈表結構！這里寫圖片描述以上，Operation 1表示移動pointer-to-pointer指向不同節點的指針域，operation 2表示修改節點的指針域，讓指向新的node。這里最大的不同是，指針是低層次的，指向指針的指針是高層次的，更靈活，兩者不是一個級別的事物！如果鏈表操作中同時需要這兩個操作，就應該考慮用pointer-to-pointer

//方法1：dummy節點class Solution {public: ListNode* removeElements(ListNode* head, int val) { // ListNode node(0); ListNode* dummy=&node; dummy->next=head; head=dummy; while(head->next){ if(head->next->val==val){ head->next=head->next->next; }else head=head->next; } return node.next; }};//方法1.1：dummy節點,下面也行。但是需要delete dummy.不如上面方法來得快！class Solution {public: ListNode* removeElements(ListNode* head, int val) { // ListNode* dummy=new ListNode(0); dummy->next=head; head=dummy; while(head->next){ if(head->next->val==val){ head->next=head->next->next; }else head=head->next; } head=dummy->next; delete dummy; return head; }};//方法2：pointer-to-pointerclass Solution {public: ListNode* removeElements(ListNode* head, int val) { // ListNode** pp=&head; while(*pp){ if((*pp)->val==val){ *pp=(*pp)->next; }else pp=&((*pp)->next); } return head; }};

上一篇：51Nod - 1523 構造

下一篇：有序廣播的知識運用