Delete Node In List

发表于 | 分类于

Delete Node In List(删除链表中指定值的节点)

题目描述：

给定一个链表的头结点，和一个目标值。要求将链表中与目标值相同的节点全部删除。

例子：

链表为1->1->2->3->1->1->2->NULL；目标值为1，则删除后的链表为：2->3->2->NULL。

解题思路1：

第一种解题思路是将链表中的节点依次的压入栈，在压栈的过程中判断当前节点是否和目标值相同，相同的节点不入栈。然后从栈顶不断取出元素将其重新连接起来将头结点返回即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class removeSpecificValue1{
public:
    ListNode* removeSpecificValue(ListNode* head, int value){
        std::stack<ListNode*> stk;//定义栈用于保存元素
        while(head != NULL){
            if (head->val != value){
                stk.push(head);
                head = head->next;
            }
            else
                head = head->next;
        }                     //将元素不断入栈
        while(!stk.empty()){
            stk.top()->next = head;
            head = stk.top();
            stk.pop();
        }                   //重新连接元素
        return head;
    }
};

解题思路2：

在考虑不用额外空间的情况下，我们的做法是遍历链表的过程中直接将该元素删除即可。需要注意的地方在于开头需要先找到不等于目标值的节点，还有记录删除节点的上一个节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class removeSpecificValue1{
public:
    ListNode* removeSpecificValue(ListNode* head, int value){
        if (head == NULL)
            return head;
        while(head != NULL){
            if (head->val != value){
                break;
            }
            else{
                head = head->next;
            }
        }  // 找到第一个节点作为开头
        ListNode* pre = head; // 记录删除节点的前一个节点
        ListNode* cur = head->next;
        while(cur != NULL){
            if (cur->val == value){
                pre->next = cur->next;
                cur = pre->next;
            }
            else{
                pre = pre->next;
                cur = cur->next;
            }
        }
        return head;
    }
};