452. 删除链表中的元素基本操作。链表

和蔼的zhxing

发布于 2018-09-04 13:05:14

8730

发布于 2018-09-04 13:05:14

删除链表中等于给定值val的所有节点。样例给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。

基本操作。

找到这个数，并且把其前后两个连起来，就可以了。遍历的时候用当前数据比较的话会丢失掉前一个节点的信息，所以我们用current->next->val作为遍历的主体，这样我们在头节点之前加一个假的节点。然后把这个节点的位置保存起来，再进行遍历：

 ListNode *removeElements(ListNode *head, int val)
    {
        if(head==NULL)
        return NULL;
        ListNode *first;
        first->next=head;
        head=first;
        while(head->next!=NULL)
        {
            if(head->next->val==val)
            {
                head->next=head->next->next;
            }
            else
            head=head->next;
        }
        return first->next;
        
    }

也可以不借助这个假节点，但是头节点要单独检查：

ListNode *removeElements(ListNode *head, int val) {
        // Write your code here
        while(1)
        {
            if ( head == NULL ) 
            return NULL;
            
            if(head->val==val)
            head=head->next;
            else 
            break;
        }
        if ( head == NULL ) {
            return NULL;
        } 
        auto current=head;
        while(current->next!=NULL)
        {
            if(current->next->val==val)
            {
                current->next=current->next->next;
            }
            else
            current=current->next;
        }
        return head;
    }

稍微麻烦一点，还是推荐使用假头节点的写法，简单一些。

链表

链表有很多种，这里给的是单向链表，链表由节点构成，每一个节点包含两个信息，分别是数据和链（实际上就是一个指针，指向下一个节点，如果没有下一个这个指针为NULL）。

* Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };

这是题目中给出的一个单向链表节点，数据类型为int。附带一个构造函数。除此之外还有双向链表（每一个链表有两条链，分别指向前一个和后一个节点），循环链表也是有的，就是收尾又链接起来，显而易见是有单向循环也有双向循环的。

链表的优点：

插入删除方便，只要改变指针的指向就可以，不用像数组一样需要移动数据。

链表的缺点：

因为内存不连续，所以查找效率不高。

它的优缺点和数组刚好是反过来的。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.01.03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度