描述

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

分析

先构造一个链表结点dummyHead，并让这个结点“插到”原链表头结点之前。举个例子：假设原链表是

1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6

通过dummyHead->next=head让原链表前多了这个结点，以方便操作：

INT_MIN --> 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6

再用一个指针cur指向这个新的链表的头结点，每次做如下操作：

cur是否为空？若为空，退出循环，否则进入下一步；
cur->next是否为空？若为空，说明已遍历完链表，令cur=cur->next，退出循环；否则，继续判断cur->next->val是否等于给定的值val，若不相等，则遍历下一元素，即令cur=cur->next。若相等，说明找到该元素，进行删除结点操作。
为了删除当前结点，需要用一个临时结点tmp指向该结点，然后让cur“跳过”该结点，跳过后，删除该结点，否则会造成内存泄漏。删除操作结束后，继续下一次循环。

代码如下：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* removeElements(ListNode* head, int val) {

        ListNode* dummyHead = new ListNode(INT_MIN);    //create a node as "new head"

        dummyHead -> next = head;

        ListNode* cur = dummyHead;

        while(cur){

            if(cur -> next && cur -> next -> val == val){   //be sure of that cur -> next is valid

                ListNode* tmp = cur -> next;    //store the node we want to delete

                cur -> next = tmp -> next;

                delete tmp;     //delete the node or it may cause memory leak

            }else

                cur = cur -> next;  //otherwise modify cur

        }

        return dummyHead -> next;

    }

};

巴特西

leetcode解题报告（28）：Remove Linked List Elements

描述

分析

最新文章

热门文章