代码随想录算法训练营第三天 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

今日任务：

链表理论基础
LeetCode203 移除链表元素
LeetCode707 设计链表
LeetCode206 反转链表

资料来源：

代码随想录 | LeetCode203 移除链表元素

代码随想录 | LeetCode707 设计链表

代码随想录 | LeetCode206 反转链表

1 LeetCode203 移除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

一开始没想那么多，直接就遍历然后写了，碰见一个删一个。

python
# 我的代码
from typing import Optional

# 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]:
        point = head
        if head is None:
            return head
        while point.next is not None:
            if point.next.val == val and point.next.next is not None:
                point.next = point.next.next
            elif point.next.val == val and point.next.next is None:
                point.next = None
            elif point.next.val != val:
                point = point.next
        if head.val == val:
            return head.next
        return head

写完之后看了文档，才知道虚拟头节点这个技巧。在链表原本的头节点之前加一个虚拟头节点，在针对头节点和尾节点进行处理时比较方便。

python
from typing import Optional

# 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]:
        # 虚拟头节点
        virtual_head = ListNode(next=head)
        point = virtual_head
        while point.next is not None:
            if point.next.val == val:
                point.next = point.next.next
            else:
                point = point.next
        return virtual_head.next

2 LeetCode707 设计链表

题目

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：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 的节点。

示例：


输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 * 2000 。

原本以为很快就能写完的，然后被爆杀。主要原因还是对各个方法主要的要循环的区间和实际要操作的元素不清。

get方法：它能接收的查找index就是0到max_index，进行循环的区间也是从实际链表的头节点开始即可。
addAtHead方法：它实际要对虚拟头节点进行处理。
addAtTail方法：它实际要对最后一个节点进行处理。
addAtIndex方法：它能接收的查找index就是0到max_index + 1，但是进行循环的区间是从虚拟头节点开始到最后一个节点。它实际要对index - 1处的节点进行处理。
deleteAtIndex方法：它能接收的查找index是0到max_index，进行进行循环的区间是从虚拟头节点开始到倒数第二个节点。它实际要对index - 1处的节点进行处理。

python
# 我的代码
class Node:
    def __init__(self, val: int = 0, next: 'Node' = None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.virtual_head = Node()
        self.max_index = -1  # 最大允许的索引


    # def test(self):
    #     print("test")
    #     if self.virtual_head.next is None:
    #         return
    #     point = self.virtual_head.next
    #     while point.next is not None:
    #         print(point.val)
    #         point = point.next
    #     print(point.val)
    #     print("\n", end="")


    def get(self, index: int) -> int:
        # self.test()
        # 判断是否合法
        if index > self.max_index:
            return -1
        point = self.virtual_head.next
        for _ in range(index):
            point = point.next
        return point.val


    def addAtHead(self, val: int) -> None:
        # self.test()
        new_node = Node(val, self.virtual_head.next)
        self.virtual_head.next = new_node
        self.max_index += 1


    def addAtTail(self, val: int) -> None:
        # self.test()
        # 实际要处理的是最后一个节点 point需要指向最后一个节点
        new_node = Node(val, None)
        point = self.virtual_head
        for _ in range(self.max_index + 1):
            point = point.next
        point.next = new_node
        self.max_index += 1


    def addAtIndex(self, index: int, val: int) -> None:
        # self.test()
        # 实际要处理的是index-1位置上的节点 point需要指向这里
        # 判断合法
        if index > self.max_index + 1 or index < 0:  # 因为addAtIndex 也可以在末尾添加 末尾对应的就是max_index + 1
            return
        elif index == 0:
            self.addAtHead(val)
            return
        point = self.virtual_head.next
        for _ in range(index - 1):
            point = point.next
        new_node = Node(val, point.next)
        point.next = new_node
        self.max_index += 1


    def deleteAtIndex(self, index: int) -> None:
        # self.test()
        # 实际要处理的是index-1位置上的节点 point需要指向这里
        # 判断合法
        if index > self.max_index or index < 0:
            return
        point = self.virtual_head  # 这里想清楚deleteAtIndex的要处理的范围 它是可能要处理virtual_head的
        for _ in range(index):
            point = point.next
        if index == self.max_index:
            point.next = None
        else:
            point.next = point.next.next
        self.max_index -= 1

再把代码随想录的简洁python代码贴在这：

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

3 LeetCode206 反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：


输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：


输入：head = [1,2]
输出：[2,1]

示例 3：


输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

一开始想不到思路，只好暴力破解，多开一个链表另存数据。

python
# 我的代码
from typing import Optional

# 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]:
        if head is None:
            return None
        new_reverse_list_after = ListNode(head.val)
        while True:
            if head.next is not None:
                head = head.next
                new_reverse_list_before = ListNode(head.val, new_reverse_list_after)
                new_reverse_list_after = new_reverse_list_before
            else:
                break
        return new_reverse_list_after

最快解法是运用三个指针来进行元素指向的反转。一次反转过程是这样的：

初始状态下，before指向上一个已经反转完成的节点，after指向准备反转的节点。
使temp指向after的下个节点
使after所指向的节点反转指向before
使before指向after所指向的节点
使after指向temp所指向的节点。

python
from typing import Optional

# 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]:
        before = None
        after = head
        while after:
            temp = after.next
            after.next = before
            before = after
            after = temp
        return before

另外这个递归也没确实想过，贴在这里。

python
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)  # 使下一个节点开始反转

目录

1 LeetCode203 移除链表元素

2 LeetCode707 设计链表

3 LeetCode206 反转链表