首页 > 其他分享 >代码随想录训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表

代码随想录训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表

时间:2024-06-07 21:21:48浏览次数:28  
标签:cur val self 随想录 next 链表 移除 节点

python定义链表
val:数据域,节点存储的元素。
next:指针域,指向下一个节点的指针,最后一个节点指向None表示空指针。

点击查看代码
class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

203.移除链表元素

题目:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

解题:

思路:要区别是不是头节点。可以按两个规则来删除,也可以使用虚拟头节点统一规则。
一、两个规则

  1. 要删除的点是头结点,移动head:移除头节点是持续操作,有可能前几个值一样,用while不是if。
  2. 要删除的点不是头结点,移动cur:临时指针cur应该指向head,cur=head,而不是该删除的节点,不然找不到删除节点的上一个节点。
    二、虚拟头节点,更简单!
  3. 定义一个虚拟头节点:dummy_head = ListNode(next = head),头结点没有值!
  4. cur=dummyhead,而不是dummyhead→next,原因同上
  5. return dummyNode->next,不要return head,head已经不是我们的头节点了
    画个图好理解!!dummy、head都相当于一个指针下标
点击查看代码
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummyhead=ListNode(next=head)
        cur=dummyhead
        while cur.next:
            if cur.next.val==val:
                cur.next=cur.next.next
            else:
                cur=cur.next
        return dummyhead.next

707.设计链表

题目:你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类:
MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。

解题:

思路:

  1. get:cur=dummyhead.next,为了方便从第一个实际节点开始遍历,return cur.val
  2. 报错:index>self.size而不是>=
点击查看代码
class MyLinkedList:

    def __init__(self):
        self.dummyhead=ListNode()
        self.size=0

    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1
        cur=self.dummyhead.next
        for i in range(index):
            cur=cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        new=ListNode(val,next=self.dummyhead.next)
        self.dummyhead.next=new
        self.size+=1

    def addAtTail(self, val: int) -> None:
        cur=self.dummyhead
        while cur.next:
            cur=cur.next
        new=ListNode(val,next=None)
        cur.next=new
        self.size+=1

    def addAtIndex(self, index: int, val: int) -> None:
        if index<0 or index>self.size:
            return
        cur=self.dummyhead
        for i in range(index):
            cur=cur.next
        new=ListNode(val,next=cur.next)
        cur.next=new
        self.size+=1

    def deleteAtIndex(self, index: int) -> None:
        if index<0 or index>=self.size:
            return
        cur=self.dummyhead
        for i in range(index):
            cur=cur.next
        cur.next=cur.next.next
        self.size-=1

206.反转链表

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

解题:

一、双指针法

  1. cur=head,pre=None
  2. cur.next=pre,如果cur指向pre,那么cur和下一个节点的连接就没有了,所以需要一个临时指针temp在赋值前保存cur的下一个节点
  3. 先移动pre,再移动cur
点击查看代码
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
         cur=head
         pre=None
         while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
         return pre

二、递归法:在双指针法基础上写的,一一对应,但是比较晦涩难懂,看一下蒜了。

点击查看代码
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

心得:
增删:cur=dummyhead,指向要插入的前一个节点
查找:cur=dummyhea.next,方便从第一个实际节点开始比较

标签:cur,val,self,随想录,next,链表,移除,节点
From: https://www.cnblogs.com/MengyiSun/p/18237895

相关文章

  • 代码随想录算法训练营第30天|回溯复习篇
    回溯基础理论1.回溯的本质是利用递归进行暴力搜索,将符和条件的结果集搜索出来2.回溯法常见的问题:组合问题:N个数里面按一定规则找出k个数的集合排列问题:N个数按一定规则全排列,有几种排列方式切割问题:一个字符串按一定规则有几种切割方式子集问题:一个N个数的集合里有多少符合......
  • 二叉链表---二叉树的简单实现
    实验内容将二叉链表视为森林的孩子兄弟链表,计算森林中叶子个数。代码实现#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineElemTypeinttypedefstructBtree{ ElemTypeelem; structBtree*lchild,*rchild......
  • 代码随想录算法训练营第三十天 | 51.N 皇后
    51.N皇后题目链接文章讲解视频讲解递归三部曲递归函数参数需要传入当前chessBoard和棋盘大小n,以及当前要放置皇后的行数rowvoidbacktracking(vector<string>&chessBoard,intn,introw);递归终止条件当最后一个皇后放置好后结束if(row==n){result.push_b......
  • 141. 环形链表
    /***Definitionforsingly-linkedlist.*typeListNodestruct{*Valint*Next*ListNode*}*/funchasCycle(head*ListNode)bool{listMap:=map[*ListNode]struct{}{}forhead!=nil{if_,ok:=listMap[head];ok{......
  • 21. 合并两个有序链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}//创建链表funccreateList(nums[]int)*ListNode{ head:=&ListNode{} tail:=head fori:=0;i<len(nums);i++{ node:=&ListNode{Val:nums[i]} t......
  • 206. 反转链表
    packagemainimport"fmt"typeListNodestruct{ Valint Next*ListNode}funcreverseList(head*ListNode)*ListNode{ varpre*ListNode//前驱节点指针 cur:=head//当前节点指针 forcur!=nil{ next:=cur.Next//临时存储next指针 cur.N......
  • 数组大扫雷行动:JavaScript中的高效移除指定元素
    数组大扫雷行动:JavaScript中的高效移除指定元素基本概念:移除元素,何为?方法一:splice()大法方法二:filter()轻功功能使用角度与技巧案例一:简单移除案例二:条件移除实战分析遇到的坑与对策结语与讨论在JavaScript编程的征途中,数组是我们的常伴,而“移除元素”这一任务,则像......
  • 代码随想录算法训练营第七天 | 四数之和、赎金信、三数之和、四数之和2
    代码随想录算法训练营第七天383赎金信https://leetcode.cn/problems/ransom-note/submissions/537782865/383赎金信代码随想录https://programmercarl.com/0383.赎金信.html#思路四数之和2https://leetcode.cn/problems/4sum-ii/四数之和2代码随想录https://programmerca......
  • 代码随想录算法训练营第八天 | 字符串:344反转字符串、
    反转字符串https://leetcode.cn/problems/reverse-string/反转字符串代码随想录https://programmercarl.com/0344.反转字符串.html#算法公开课反转字符串题目编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外......
  • leetcode19删除链表的倒数第 N 个结点
    本文主要讲解删除链表倒数第n个节点的要点与细节c++与java代码如下,末尾本题之前可以尝试leetcode203移除链表元素具体要点:1.首先,单看移除链表节点,核心操作是:cur->next=cur->next->next 即,当前节点cur的下一个节点指向原本的下下个节点小细节:操作时,我们需要得到要......