首页 > 编程语言 >算法打卡|Day3 链表part01

算法打卡|Day3 链表part01

时间：2023-09-23 21:35:30浏览次数：44  
标签：ListNode cur val part01 next 链表 int Listnode 打卡

Day3 链表part01

今日任务
● 链表理论基础
● 203.移除链表元素
● 707.设计链表
● 206.反转链表

[TOC]

链表理论基础

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

重点：

  1. 单链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
    image
//单链表实现代码

#include <iostream>

using namespace std;

struct Node
{
    int val;
    Node* next;
} *head;

int main()
{
    for (int i = 1; i <= 5; i ++ )
    {
        Node* p = new Node();
        p->val = i;
        p->next = head;
        head = p;
    }

    for (Node* p = head; p; p = p->next)
        cout << p->val << ' ';
    cout << endl;

    return 0;
}

Problem: 203. 移除链表元素

思路

首先最原始的思路是我们可以将头结点和后面的结点分开处理。但是为了逻辑统一我们可以用虚拟头结点的方式删除链表指定元素。

解题方法

虚拟头结点

Code


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

/**
时间复杂度: O(n)
空间复杂度: O(1)
*/
class Solution {
public:
  ListNode* removeElements(ListNode* head, int val) {
      ListNode* dummy = new ListNode(-1);//涉及到单向链表头结点可以用虚拟头结点的技巧
      dummy->next = head;
      ListNode* i = dummy;
      while(i->next!=nullptr){
          if(i->next->val == val){
              //记住用临时变量保存删除
              ListNode* tmp = i->next;
              i->next = i->next->next;
              delete tmp;
          } else{
              i = i->next;
          }
      }
      //利用虚拟头结点时候要注意最后真实的头结点是由虚拟头结点确定的，所以要记得更新再释放
      head = dummy ->next;
      delete dummy;
      return head;  
  }
};

Problem: 707. 设计链表

思路

注意index下标的遍历，然后插入和删除都要在index前一位开始停下操作。

链接：
https://leetcode.cn/problems/design-linked-list/solutions/1738065/by-linken_54-7moa/

Code


class MyLinkedList {
public:
  int len;
  struct Listnode{
      int val;
      Listnode* next;
      Listnode(): val(0),next(nullptr){}
      Listnode(int _val): val(_val),next(nullptr){}
      Listnode(int _val, Listnode* _next): val(_val),next(_next){}
  };
  Listnode* dummynode;

  MyLinkedList() {
      len = 0;
      dummynode = new Listnode();
  }
  
  int get(int index) {
      if(index<0 || index >len-1) return -1;
      Listnode* cur = dummynode->next;//如果从真实头结点开始遍历，那么index--循环就是index所指示的地方
      while(index--){
          cur = cur->next;
      }
      return cur->val;
  }
  
  void addAtHead(int val) {
      if(val<0||val>1000) return;//val值无效，直接返回
      Listnode* head=new Listnode(val,dummynode->next);
      dummynode->next = head;
      len++;

  }
  
  void addAtTail(int val) {
      if(val<0||val>1000) return;//val值无效，直接返回
      Listnode* tail = dummynode;
      //遍历尾结点可以直接用tail->next去判断尾结点
      while(tail->next){
          tail = tail->next;
      }
      tail->next = new Listnode(val);
      len++;

  }
  
  void addAtIndex(int index, int val) {
      if(val<0||val>1000||index>len) return;//val值或index值无效，直接返回
      if(index<=0) addAtHead(val);//index<=0时,在头部插入值为val的新结点
      else if(index==len) addAtTail(val);//index=len时,在尾部插入值为val的新结点
      else{
          Listnode* cur = dummynode;
          while(index--) cur=cur->next;
          cur->next = new Listnode(val,cur->next);
          len++;


      }
  }
  
  void deleteAtIndex(int index) {
      if(index<0||index>len-1) return;//index值无效，直接返回
      Listnode* cur = dummynode;//如果从虚拟头结点开始遍历，那么index--循环就是index前一位所指示的地方
      while(index--){
          cur = cur->next;
      }
      Listnode* tmp = cur->next;
      cur->next = cur->next->next;
      delete tmp;
      len--;
  }
};

/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new Myb LinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/

Code2

class MyLinkedList {
private:
  struct Listnode{
      int val;
      Listnode* next;
      Listnode(): val(0),next(nullptr){}
      Listnode(int _val): val(_val),next(nullptr){}
      Listnode(int _val,Listnode* _node): val(_val), next(_node){}
  };
  int len;
  Listnode* dummyhead;
public:
  MyLinkedList(){
      len = 0;
      dummyhead = new Listnode();
  } 
  
  int get(int index) {
      if(index<0 || index > len-1) return -1;
      Listnode* cur = dummyhead->next;
      for(int i = 0;i!=index;i++){
          cur = cur->next;
      }
      return cur->val;
  }
  
  void addAtHead(int val) {
      if(val<0||val>1000) return;
      Listnode* node = new Listnode(val, dummyhead->next);
      dummyhead->next = node;
      len++;
  }
  
  void addAtTail(int val) {
      if(val<0||val>1000) return;
      Listnode* i;
      for(i =dummyhead; i->next; i = i->next){}
      i->next = new Listnode(val);
      len++;
  }
  
  void addAtIndex(int index, int val) {
      if(val<0||val>1000||index>len) return;
      if(index<=0) addAtHead(val);
      else if(index==len) addAtTail(val);
      else{
          Listnode* cur =dummyhead;
          for(int i = -1; i!=index-1; i++){
              cur = cur->next;
          }
          cur->next = new Listnode(val,cur->next);
          len++;
      }
      
  }
  
  void deleteAtIndex(int index) {
      if(index<0||index>len-1) return;
      Listnode* cur = dummyhead;
      for(int i = -1;i!=index-1; i++){
          cur = cur->next; 
      }
      Listnode* tmp = cur->next;
      cur->next =cur->next->next;
      delete tmp;
      len--;
  }
};

/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/

Problem: 206. 反转链表

思路

链表题，多画图！

好理解的双指针

1.定义两个指针： pre 和 cur ；pre 在前 cur 在后。
2.每次让 pre 的 next 指向 cur ，实现一次局部反转
3.局部反转完成之后，pre 和 cur 同时往前移动一个位置
4.循环上述过程，直至 pre 到达链表尾部

简洁的递归

1.使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
2.此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
3.同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
4.当递归函数全部出栈后，链表反转完成。

链接：https://leetcode.cn/problems/reverse-linked-list/solutions/99711/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/

解题方法

双指针和递归

Code1: 双指针

//时间复杂度: O(n)
//空间复杂度: O(1)

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* reverseList(ListNode* head) {
      ListNode* a = nullptr;
      ListNode* b = head;
      while(b){
          ListNode* tmp = b->next;
          b->next = a;
          a = b;
          b = tmp;
      }
      return a;

  }
};

Code2: 递归法

//时间复杂度: O(n), 要递归处理链表的每个节点
//空间复杂度: O(n), 递归调用了 n 层栈空间
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* reverseList(ListNode* head) {
      if(head == nullptr||head->next == nullptr) return head;
      else{
          ListNode* tail=reverseList(head->next);
          head->next->next = head;
          head->next =nullptr;
          return tail;
      }
  }
};

标签：ListNode,cur,val,part01,next,链表,int,Listnode,打卡
From： https://www.cnblogs.com/RickRuan/p/17725094.html

相关文章

  • Leetcode刷题21.合并两个有序链表
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1：输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]示例2：输入：l1=[],l2=[]输出：[]示例3：输入：l1=[],l2=[0]输出：[0] 提示：两个链表的节点数目......
  • 923打卡
    1.三数之和（15）给你一个整数数组 nums ，判断是否存在三元组 [nums[i],nums[j],nums[k]] 满足 i!=j、i!=k 且 j!=k ，同时还满足 nums[i]+nums[j]+nums[k]==0 。请你返回所有和为 0 且不重复的三元组。classSolution{publicList<List<Integer>>......
  • 随想录Day4|24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题 02.07.
    随想录Day4|24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07.链表相交、142.环形链表Ⅱ 24.两两交换链表中的节点文章讲解视频讲解给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，......
  • 【算法】链表
    1链表理论基础链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。链表中的节点在内存中不是连续分布的，而是散乱分布在内......
  • 数据结构之 - 链表数据结构详解: 从基础到实现
    链表（LinkedList）是计算机科学中常用的数据结构之一，它具有灵活的内存分配和高效的插入、删除操作。本文将深入介绍链表的特性、基本类型、操作以及在实际应用中的使用场景。1.什么是链表？链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用（或指针）。与数......
  • 打卡
    9月22日：今天上午上了形势与政策课程，下午我们学习了高级英语，通过两节课的学习，我有从中学习了单词与语法，与此同时今天我也将java课的课后作业完成。明天做数据结构与算法的课后习题，然后抽时间学习一下java。......
  • 每日打卡 周五 九月二十二日
    今天又上英语课，快要四级考试了，得抓紧学习英语，下午完课后，看了一会儿英语单词，主要是翻译有问题，以前没有做过的题型也会一直是难，主要是想不词语的意思可以那样用。其实主要功课就是背单词，现在词汇积累的少，出现都不认识，在着就是听听力，真的是要很好的训练了。......
  • 922打卡
    1.盛最多水的容器（11）给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i,0) 和 (i,height[i]) 思想：双指针classSolution{publicintmaxArea(int[]height){intleft=0;intright=height.length-1;i......
  • LeetCode3题学透链表初始化、查找、插入删除、逆置操作
    1.题目要求LeetCode203移除链表指定元素LeetCode707设计链表LeetCode206反转链表  这三个题目包含了链表的初始化、插入头尾结点、插入删除第n个结点，删除指定内容的结点、链表的逆置等，下面我将一一讲解并展示源代码。2.具体操作2.1LeetCode中链表的初始化  我下面所讲......
  • 算法打卡|Day2 数组part02
    Day2数组part02今日任务:977.有序数组的平方，209.长度最小的子数组，59.螺旋矩阵II目录Day2数组part02今日任务:977.有序数组的平方，209.长度最小的子数组，59.螺旋矩阵IIProblem:977.有序数组的平方思路解题方法复杂度CodeProblem:209.长度最小的子数组思路解题方法复杂......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99