移除链表元素 , 设计链表 ,反转链表

这篇具有很好参考价值的文章主要介绍了移除链表元素 , 设计链表 ,反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

移除链表元素

leetcode

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

示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]

示例 2: 输入:head = [], val = 1 输出:[]

示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode * hummyhead = new ListNode(0);
        hummyhead -> next = head;
        ListNode *current = hummyhead;
        while ( current -> next != NULL ) {
            if( current -> next -> val == val ) {
               ListNode * dele = current -> next ;
                current -> next = current -> next ->next ;
                 delete dele;
            }
            else current = current -> next ;

        }

  return hummyhead -> next;
    }
      
};

移除元素  主要是  找到要移除的前一个  , 之后才能移除 。采用虚拟头节点的方法 ,用current 记录比较元素的 前一个 ,如果找到元素  那current 就是前一个 ,注意 循环结束条件  。

设计链表

leetcode

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
class MyLinkedList {
public:
struct LinkedNode {
    int val;
    LinkedNode *next;
    LinkedNode ( int val ) : val(val), next(nullptr){}
};
    MyLinkedList() {
      dummyhead = new LinkedNode(0);
      size = 0;
    }
    
    int get(int index) {         // 获得指定位置的值
        if ( index < 0 || index >= size) {
            return -1;
        }
        LinkedNode *current = dummyhead -> next;
        while ( index-- ) {
            current = current -> next;
        }
        return current -> val;
    }
    
    void addAtHead(int val) {   // 在链表头添加节点
        LinkedNode *newnode = new LinkedNode(val);
        newnode -> next = dummyhead -> next;
        dummyhead -> next = newnode;
        size++;
    }
    
    void addAtTail(int val) {    //在尾部插入结点
        LinkedNode *newnode = new LinkedNode(val);
        LinkedNode *current = dummyhead;
        while ( current -> next != nullptr ) {
            current = current-> next;
        }
        current -> next = newnode;
        size++;
    }
    
    void addAtIndex(int index, int val) {   //在下表为index 处插入节点
        if ( index < 0 ) index = 0;
        if ( index > size )return ;
        LinkedNode *newnode = new LinkedNode(val);
        LinkedNode *current = dummyhead;
        while (index--) {
            current = current -> next;
        }
        newnode -> next = current -> next;
        current -> next = newnode;
        size++;
    }
    
    void deleteAtIndex(int index) {   //删除指定下标节点
        if ( index < 0 || index >= size) return;
        LinkedNode *current = dummyhead;
        while ( index-- ) {
            current = current -> next;
        }
        LinkedNode *tem = current -> next;
        current -> next = current -> next -> next;
        delete tem;
        size--;
    }
private:
    int size;
    LinkedNode * dummyhead;
};

反转链表

leetcode

反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

 可以采用 双指针 和 递归 , 递归实际是 双指针的 精简

以下是采用递归的代码

class Solution {
public:
    ListNode* digui (ListNode* current,ListNode * pre) {
        
        if ( current == nullptr ) return pre;
        ListNode* tem = current -> next;
        current -> next = pre;
        return digui(tem,current);
        
    }

    ListNode* reverseList(ListNode* head) {
     return digui(head , nullptr);
    }
};

以下是采用双指针的代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * current = head;
        ListNode *pre = nullptr;
        while ( current != nullptr ) {
            ListNode *tem = current -> next;
            current -> next = pre;
            pre = current;
            current = tem;
        }
        return pre;
        
    }
};

实际上 递归 是 把双指针的 while 简化 , 减少了对current 和 pre 的 重复 赋值

此题 关键 是要 注意 改变链表之间的连线时  要注意不要和后面的 断掉联系 ,可以用临时指针 保存后面的节点文章来源地址https://www.toymoban.com/news/detail-477429.html

到了这里,关于移除链表元素 , 设计链表 ,反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法-设计链表、移除链表元素、反转链表

    伪装成一个老手! 设计一个单链表,其中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 实现 MyLinkedList 类: MyLinkedList()初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1

    2024年02月11日
    浏览(96)
  • 203.移除链表元素|707.设计链表|206.反转链表

    203. 移除链表元素 这里以链表 1 4 2 4 来举例,移除元素4。 如果使用C,C++编程语言的话,不要忘了还要从内存中删除这两个移除的节点, 清理节点内存之后如图: 其实 可以设置一个虚拟头结点 ,这样原链表的所有节点就都可以按照统一的方式进行移除了。 来看看如何设置

    2024年02月11日
    浏览(42)
  • 203.移除链表元素&707.设计链表& 206.反转链表

    203.移除链表元素: 给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 707.设计链表  : 你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。

    2024年02月11日
    浏览(34)
  • day 3 | 203.移除链表元素、707.设计链表、206.反转链表

    目录: 链表基础:https://programmercarl.com/链表理论基础.html 题目链接: https://leetcode.cn/problems/remove-linked-list-elements/ 203. 移除链表元素 给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 自己思路:从头

    2024年02月08日
    浏览(43)
  • Day 3 链表: 203.移除链表元素, 707.设计链表, 206.反转链表

    链接基础,以及链表和数组的区别: 代码随想录 1. 链表类型: 单列表,双列表,循环列表。 单列表: 双列表: 循环列表: 2. 链表的操作 :删除节点,增加节点。 删除节点: 其中对于 普通的节点 删除,就如上图所示,直接让前一个节点的指向下一个节点即可。 但是对于

    2024年02月16日
    浏览(41)
  • Day03|链表01:203.移除链表元素、707.设计链表、206.反转链表

    今天进入链表章节的学习了,也是之前学过的内容,这次争取快速AC。 leetcode链接:https://leetcode.cn/problems/remove-linked-list-elements/ 没什么好说的,这里注意引入了一个虚拟头节点dummy,这样就不用处理需要删除第一个节点的特殊情况。删除时C++需要手动detete。我本来使用free的,

    2024年02月17日
    浏览(43)
  • 算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表

    题目链接:力扣 思路:删除链表元素与数组不同之处在于,它需要被删除链表元素的前一个元素和后一个元素的参与,而不需要其他元素的参与。 我们使被删除元素前一个元素的指针指向被删除元素的后一个元素 ,也就是直接跳过被删除的元素,来实现删除。 同时我们考

    2024年02月05日
    浏览(38)
  • day3_203移除链表元素_707设计链表_206反转链表

    链表是一种通过指针串联起的线性结构,每个节点由两部分组成: 一个数据域,一个指针域(存放指向下一节点的指针),最后一个节点的指针域指向null。 链表入口节点是头结点head。 双链表:两个指针域,指向下一节点和上一节点。( 向前向后查询) 循环链表:首尾相连

    2024年02月16日
    浏览(32)
  • day3-链表理论基础 203.移除链表元素 707.设计链表 206.反转链表

    单链表 双链表:每个节点有两个指针域,一个指向下一个节点,一个指向上一个节点 既可以查询前一个节点,又能查询后一个节点 循环列表:链表首尾相连 在内存上 不是连续分布 的,散乱分布在内存中的某地址上 删除节点:next指针直接指向下下个节点,且在内存中删除

    2024年02月04日
    浏览(32)
  • 代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

    直接让前一个节点指向后一个节点即可 两种方法 第一种:直接删除 第二种:头删的时候,直接 head=head-next 其实这两种方法都没有做到统一 第三种:虚拟头结点法 这样的话,咱们删除的时候,就是以统一的规则来进行删除啦! 203.移除链表元素 法一:原始删除法 1、while(h

    2024年02月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包