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

标签：head ListNode cur val self 随想录 next 链表移除

1 前言

今日主要学习链表的基础
leetcode 203移除链表元素
leetcode 707 设计链表
leetcode 206 反转链表

2 链表的基础

链表分为单链表和双链表，与字符串的区别就是链表是在一个里面存储了数据+下一个数据的内存地址
链表中存储的内存空间是可以不连续的

2.1 链表的定义

2.1.1 python版本

class ListNode:
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next

2.1.2 C++版本

单链表自己构造并定义的方法

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(Null) {}
};

ListNode*head =new ListNode(5)

默认构造的方法

ListNode *head = new ListNode();
head -->val = 5;

3 leetcode203 移除链表元素

题目链接：203. 移除链表元素 - 力扣（LeetCode）

文章链接：代码随想录 (programmercarl.com)

视频链接：帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili

思路：没有思路，看到这道题有一种想立马退出的感觉，无从下手

3.1 原来链表进行删除的方法

自己是完全敲不出来的那种，真的听了课程也没有跟上的章节

3.1.1 python方法

这个版本是参考了C++语法，自己改过来的版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        while head!=None and head.val == val:
            head = head.next
        cur = head
        while cur!=None and cur.next !=None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur=cur.next
        return head

3.1.2 C++方法

/**
 * 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* removeElements(ListNode* head, int val) {
        while (head!= NULL && head->val == val){
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }   
        ListNode* cur = head;
        while (cur!=NULL && cur->next!=NULL){
            if (cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{
                cur=cur->next;
            }
        }
        return head;
    }
};

3.2 新建一个虚拟头结点进行删除

3.2.1 python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next !=None:
            if cur.next.val==val:
                cur.next=cur.next.next
            else:
                cur=cur.next
        return dummy_head.next

3.2.2 C++版本

/**
 * 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* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while (cur->next != NULL){
            if (cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }

3.3单链表小结

这一部分首先就是需要了解链表是什么，其实链表逻辑就是链表存储的是数字加下一个元素的位置
单链表就是从前往后走不会回头的那种所以就不会存在我下一个数值和上一个的联系

4 leetcode707设计链表

题目链接：707. 设计链表 - 力扣（LeetCode）

文章链接：代码随想录 (programmercarl.com)

视频链接：帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili

思路：压根不会，看了视频也没有学会的一道题

4.1 单链表的方法

4.1.1 python版本

class ListNode:
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next
class MyLinkedList:

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

    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1

        current = self.dummy_head.next
        for i in range(index):
            current = current.next
        return current.val

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

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

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

    def deleteAtIndex(self, index: int) -> None:
        if index<0 or index>=self.size:
            return

        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = current.next.next
        self.size -=1
        


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

4.2 链表设计小结

这一道题是真的好难，完全没有思路的那种，对着别人的思路进行复现了一下，然后理解了别人里面的基本逻辑，但是具体的，怎么说呢，还是得明天复习，发现从这一章开始变难了，我只能先完成python版本的了，C++等二刷的时候，我再去重新学习重新写吧

5 leetcode206.反转链表

5.1 双指针的方法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        current = head
        while current:
            tmp = current.next
            current.next = pre
            pre = current
            current = tmp
        return pre

5.2递归思想

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.reverse(None,head)
    def reverse(self,pre:ListNode,cur:ListNode)->ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(cur,temp)

5.3 小结

这一部分的递归思想我听懂了，但是代码实现过程中，其实很绕很绕还是不是很会写

6.总结

6.1 代码总结

主要就是调用链表中的存储位置是humlenth.next
调用链表中的值是humlenth.next.val
python方法定义一个链表的代码是

class ListNode():
    __init__(self,val=0,next=None):
        self.val = val
        self.next = next

6.2方法思路总结

首先注意链表其实是一个给定的值和存储空间用一根线连接的，所以在使用链表的时候就是注意他的值和存储空间即head的位置
其实现在回想这几道题，思路其实挺清晰的就是不会写，嗯，递归的方法等周末有时间了还得复习，写的真的不是很好

标签：head,ListNode,cur,val,self,随想录,next,链表,移除
From： https://www.cnblogs.com/csfy0524/p/18475129