LeetCode刷题记：链表

作者： 千石 支持：点赞、收藏、评论 欢迎各位在评论区交流

前言

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

一些话

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

题目练习步骤：

1. 给自己10分钟，读题并思考解题思路
2. 有了思路以后开始写代码，如果在上一步骤中没有思路则停止思考并且看该题题解
3. 在看懂题解（暂时没看懂也没关系）的思路后，背诵默写题解，直至能熟练写出来
4. 隔一段时间，再次尝试写这道题目

刷题

707. 设计链表 - 力扣（LeetCode）

题意：

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

-   get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-   addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-   addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-   addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-   deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

题解

1. 对于 get(index) 方法，我们需要遍历链表，找到第 index 个节点，然后返回该节点的值。如果 index 小于 0 或大于等于链表长度，则返回 -1。时间复杂度为 O(n)，其中 n 是链表的长度。
2. 对于 addAtHead(val) 方法，我们需要创建一个新的节点，并将它的 next 指针指向原来的头节点。然后将头节点指向新的节点。时间复杂度为 O(1)。
3. 对于 addAtTail(val) 方法，我们需要遍历整个链表，找到最后一个节点，然后将其 next 指针指向一个新的节点。时间复杂度为 O(n)。
4. 对于 addAtIndex(index, val) 方法，我们需要遍历链表，找到第 index-1 个节点。然后我们创建一个新的节点，并将其 next 指针指向第 index 个节点。最后将第 index-1 个节点的 next 指针指向新的节点。时间复杂度为 O(n)，其中 n 是链表的长度。
5. 对于 deleteAtIndex(index) 方法，我们需要遍历链表，找到第 index-1 个节点，然后将它的 next 指针指向第 index+1 个节点。时间复杂度为 O(n)，其中 n 是链表的长度。

代码实现如下：

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 定义链表类
class MyLinkedList:
    def __init__(self):
        """
        在此处初始化你的数据结构。
        """
        self.head = None
        self.tail = None
        self.length = 0

    def get(self, index: int) -> int:
        """
        获取链表中第 index 个节点的值。如果索引无效，则返回-1。
        """
        if index < 0 or index >= self.length:
            return -1
        cur = self.head
        for i in range(index):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        """
        在链表的开头插入一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
        """
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.length += 1

    def addAtTail(self, val: int) -> None:
        """
        将值为 val 的节点追加到链表的最后一个元素。
        """
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1

    def addAtIndex(self, index: int, val: int) -> None:
        """
        在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
        """
        if index > self.length:
            return
        if index <= 0:
            self.addAtHead(val)
        elif index == self.length:
            self.addAtTail(val)
        else:
            new_node = ListNode(val)
            cur = self.head
            for i in range(index - 1):
                cur = cur.next
            new_node.next = cur.next
            cur.next = new_node
            self.length += 1

    def deleteAtIndex(self, index: int) -> None:
        """
        如果索引有效，则删除链表中的第 index 个节点。
        """
        if index < 0 or index >= self.length:
            return
        if index == 0:
            self.head = self.head.next
            if not self.head:
                self.tail = None
        else:
            cur = self.head
            for i in range(index - 1):
                cur = cur.next
            cur.next = cur.next.next
            if index == self.length - 1:
                self.tail = cur
        self.length -= 1

206. 反转链表 - 力扣（LeetCode）

题意：反转一个单链表。

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

题解

本题比较简单，有多种方式可以解决，这里介绍两种： 迭代方式：

1. 定义两个指针，一个指向当前节点，一个指向前一个节点，初始化为None。
2. 循环遍历链表，将当前节点的next指针指向前一个节点。
3. 将前一个节点指针和当前节点指针都向后移动一个节点。
4. 当当前节点为None时，遍历结束，返回新的头节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

递归方式：

1. 递归到链表尾部，返回新的头节点。
2. 将当前节点的next节点的next指针指向当前节点，将当前节点的next指针置为None。
3. 返回新的头节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

24. 两两交换链表中的节点 - 力扣（LeetCode）

题解

1. 定义一个虚拟节点 dummy，指向链表头节点，用于链表交换时记录新的头节点。
2. 定义两个指针 prev 和 curr，分别指向需要交换的相邻节点的前一个节点和当前节点。
3. 循环遍历链表，如果当前节点和下一个节点不为空，则进行交换，交换完后需要更新 prev 和 curr 的位置。
4. 返回新的头节点，即 dummy.next。

代码实现如下

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 定义虚拟节点，方便链表操作
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        curr = head

        while curr and curr.next:
            next_node = curr.next
            prev.next = next_node
            curr.next = next_node.next
            next_node.next = curr
            prev = curr
            curr = curr.next

        return dummy.next