526互联

算法打卡|Day3 链表part01

发布时间 2023-09-23 21:28:13作者: RickRuan

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;

  }
};

Code1=2: 递归法

//时间复杂度: 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;
      }
  }
};