从零开始算法之路 ----移除链表元素

短命女 2022-01-25 22:57 209阅读 0赞

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（[https://leetcode-cn.com/problems/remove-linked-list-elements/][https_leetcode-cn.com_problems_remove-linked-list-elements]）

题目描述：

删除链表中等于给定值 ***val ***的所有节点。

**示例:**

输入: 1->2->6->3->4->5->6, val = 6
    输出: 1->2->3->4->5

解决方案一：非递归  
思路(笨办法，大佬轻喷)：分四种情况考虑。特殊情况：链表为空或者链表只有一个节点，并且节点值等于要移除元素的值，返回空；第一种情况，要移除的元素在头节点；第二种情况，要移除的元素是中间节点（在头节点和尾节点之间）；第三种情况，要移除的元素在尾节点。情况考虑清楚，用相应的方法移除元素即可，具体方法看代码。

/**
     * 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) {               		       
            //第一种情况：链表不为空、链表至少有两个节点并且要移除的元素在头节点
            while(head != NULL && head->next != NULL ){
                if(head->val == val)
                    head = head->next;
                else
                    //如果要移除的元素不在头节点，跳出循环
                    break;
            }
            //特殊情况：链表为空或者链表只有一个节点，并且节点值等于要移除元素的值，返回空
            if(head == NULL || head->next == NULL && head->val == val )
    		    return NULL;
            //第二种情况，要移除的元素是中间节点（在头节点和尾节点之间）
            //定义两个指针，pre 永远在current 的前一个节点
    		ListNode *current = head;
    		ListNode *pre = head;     
    		while(current != NULL &&current->next != NULL ){
                //保证pre 在current 的前一个节点
                if(pre == current && current->val != val)
                    current = current->next;
    			//把要移除的链表元素从链表种移除
    			if(current->val == val){                
                        pre->next = current->next;
                }
                //如果current 指向最后一个节点，跳出循环
                if(current->next == NULL)
                    break;
                //继续寻找下个元素判断是否为要移除链表元素
    			current = current->next;
                //保证pre 在current 的前一个节点
    			if(current->val != val || pre->next != current)
    			   pre = pre->next;
    		}
            // current 指向链表最后一个节点，
            //第三种情况，要移除的元素在尾节点，移除尾节点
            if( current->val == val)
                pre->next = NULL;
    		return head;
        }
    };

解决方案二：递归

思路：

1.找终止条件：当head指向链表为空，return  
2.返回什么值：应该返回的自然是已经移除指定元素链表的头节点  
3.每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个移除指定元素链表的头节点。因此这一步应该做的是判断当前的head->val和val是否相等，如果相等则说明要移除，返回head.next，否则返回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) {
            if(head == NULL)
                return head;
            head->next = removeElements( head->next,  val);
            return head->val == val ? head->next:head;
            
        }
    };

[https_leetcode-cn.com_problems_remove-linked-list-elements]: https://leetcode-cn.com/problems/remove-linked-list-elements/