LeetCode 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
思路分析:扫描链表,如果节点值与val相同则释放这个节点,否则放到新链表中。
/**
* 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) {
//pHead指向结果链表的表头,pEnd指向结果链表的表尾
ListNode *pHead = NULL, *pEnd = NULL, *tempPtr = NULL;
while (head != NULL) {
tempPtr = head;
head = head->next;
//如果节点值是val,则需要释放
if (tempPtr->val == val) {
delete tempPtr;
continue;
}
//将tempPtr放入结果链表的尾端
if (pHead == NULL) {
pHead = pEnd = tempPtr;
}
else {
pEnd->next = tempPtr;
pEnd = pEnd->next;
}
}
//最后链表需要封尾
if (pEnd != NULL) {
pEnd->next = NULL;
}
return pHead;
}
};
方法二:直接在原链表中移除值为val节点。
/**
* 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 *tempPtr = NULL, *ptr = NULL;
//寻找到第一个值不为val的节点
while (head != NULL && head->val == val) {
tempPtr = head;
head = head->next;
delete tempPtr;
}
ptr = head;
//扫描剩余的节点
while (ptr != NULL) {
//如果此节点后的节点值等于val,则将此节点从链表剔除并释放
if (ptr->next != NULL && ptr->next->val == val) {
tempPtr = ptr->next;
ptr->next = ptr->next->next;
delete tempPtr;
}
else {
ptr = ptr->next;
}
}
return head;
}
};
方法三:递归实现。
/**
* 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 *tempPtr = NULL;
if (head == NULL){
return NULL;
}
//如果当前节点值等于val
if (head->val == val){
tempPtr = head;
head = removeElements(head->next, val);//去除head后面的值为val节点
delete tempPtr;//释放这个节点
}
else{
head->next = removeElements(head->next, val);//去除head后面的值为val节点
}
return head;
}
};