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

链表理论基础

链表的类型

单链表

每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

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

 203.移除链表元素

力扣题目链接(opens new window)

题意：删除链表中等于给定值 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 ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:

    def removeElements(self, head: ListNode, val: int) -> ListNode:
        while head is not None and head.val == val:
            head = head.next

        if head is None:
            return head

        cur = head
        while (cur.next != None):
            if (cur.next.val == val):
                cur.next = cur.next.next  # 删除cur.next节点
            else:
                cur = cur.next
        return head

707.设计链表

力扣题目链接(opens new window)

题意：

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

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

代码

照着给的默写了一遍，应该是会了

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
        cur = self.dummy_head.next
        for _ in range(index):
            cur = cur.next  # cur指向index位置
        return cur.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:
        cur = self.dummy_head
        while cur.next:
            cur = cur.next  # cur指向最后一个节点
        cur.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:  # index大于size时，相当于在尾部插入节点
            return
        cur = self.dummy_head
        for _ in range(index):
            cur = cur.next
        cur.next = ListNode(val, cur.next)  # 在cur和cur.next之间插入节点
        self.size += 1

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

        cur = self.dummy_head
        for _ in range(index):  # cur指向index位置的前一个节点
            cur = cur.next
        cur.next = cur.next.next
        self.size -= 1

#代码随想录算法训练营/第三天/206.反转链表 #算法/链表

206.反转链表

力扣题目链接(opens new window)

题意：反转一个单链表。

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

代码

我一开始是想着建立两个链表，然后又想到了递归，直到这里给了个双指针法，当然递归也能做。这里用的是递归哦。

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


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(None, head)

    def reverse(self, pre: ListNode, cur: ListNode) -> ListNode:
        if cur is None:  # 递归终止条件,如果pre为空，则说明已经到达链表尾部，返回pre
            return pre
        # 将当前节点的next指针指向pre
        temp = cur.next
        cur.next = pre
        #  temp.next = cur 因为temp可能是None所以需要遍历
        return self.reverse(cur, temp)