[数据结构与算法][LeetCode] 203.移除链表元素

LeetCode 203.移除链表元素

链表的定义

定义链表结点

//单链表
struct ListNode {
  int val;			//节点上存储的元素
  ListNode *next;	//指向下一个节点的指针
  ListNode(int x) : val(x), next(NULL){}	//节点的构造函数（以初始化列表的形式进行构造函数的定义）
};

注： 若不定义构造函数，而是用C++的默认构造函数，在初始化的时候就不能直接给变量赋值！

例如：

1）通过自定义构造函数初始化节点：

ListNode *head = new ListNode(5);

2）通过C++默认构造函数初始化节点：

ListNode *head = new ListNode();
head->val = 5;

LeetCode 203.移除链表元素

LeetCode 203.移除链表元素

思路

链表的删除操作有两种方式：
1）直接使用原来的链表来进行删除操作
2）设置一个虚拟头结点再进行删除操作

删除结点：让当前节点的next指针（cur->next）直接指向下下一个节点（cur—>next->next），
		就可以把原来当前指针的下一个结点删除

对于删除头结点的操作与删除内部元素的操作不一样：
	头结点的删除只要将头结点向后移动一位即可，从而删除了一个头结点
	（注意，对于节点的删除需要将被删除结点的内存进行手动释放）
	
若希望删除头结点的操作和删除内部元素的操作一致，可以通过设置一个虚拟头结点的方式进行删除操作！
（注意：最后在 return头结点的时候，需要改为 return dummyNode->next;）

代码

1）直接使用原来的链表进行删除操作

要注意头结点和非头结点的不同删除操作！

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

2）先设置虚拟头结点，再进行删除操作

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};