链表mark

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

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

如图所示：

链表1

链表的类型

接下来说一下链表的几种类型:

单链表

刚刚说的就是单链表。

双链表

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

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

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

如图所示：

链表2

循环链表

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

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

链表4

链表的存储方式

了解完链表的类型，再来说一说链表在内存中的存储方式。

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

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

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

如图所示：

链表3

这个链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的定义

接下来说一说链表的定义。

链表节点的定义，很多同学在面试的时候都写不好。

这是因为平时在刷leetcode的时候，链表的节点都默认定义好了，直接用就行了，所以同学们都没有注意到链表的节点是如何定义的。

而在面试的时候，一旦要自己手写链表，就写的错漏百出。

这里我给出C/C++的定义链表节点方式，如下所示：

链表的操作

删除节点

删除D节点，如图所示：

链表-删除节点

只要将C节点的next指针指向E节点就可以了。

那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。

添加节点

如图所示：

链表-添加节点

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

再把链表的特性和数组的特性进行一个对比，如图所示：

链表-链表与数据性能对比

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

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

例题：

203. 移除链表元素

简单

给你一个链表的头节点 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

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

# 移除链表中指定值的节点的函数
def removeElements(head: ListNode, val: int) -> ListNode:
    # 创建一个虚拟头节点，方便处理头节点可能被删除的情况
    dummy = ListNode(next=head)
    prev = dummy  # 前一个节点
    curr = head  # 当前节点

    while curr:  # 只要当前节点不为空
        if curr.val == val:  # 如果当前节点的值等于要删除的值
            prev.next = curr.next  # 将前一个节点的下一个指针指向当前节点的下一个
        else:
            prev = curr  # 否则，更新前一个节点
        curr = curr.next  # 移动到下一个节点

    return dummy.next  # 返回新的头节点

# 示例用法
head1 = ListNode(1, ListNode(2, ListNode(6, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))))
print(removeElements(head1, 6))

head2 = ListNode()
print(removeElements(head2, 1))

head3 = ListNode(7, ListNode(7, ListNode(7, ListNode(7))))
print(removeElements(head3, 7))

这段代码的逻辑是：使用一个虚拟头节点 dummy 来简化处理。通过两个指针 prev（前一个节点）和 curr（当前节点）遍历链表。如果当前节点的值等于目标值，就跳过当前节点，将前一个节点的下一个指针指向当前节点的下一个；否则就更新前一个节点。最后返回虚拟头节点的下一个节点，即新的头节点。

空间复杂度为 O(1)，因为只使用了固定的额外空间来存储虚拟头节点和两个指针。时间复杂度为 O(n)，需要遍历整个链表一次。

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 的节点。

示例：

输入
["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 。

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

class MyLinkedList:
    def __init__(self):
        # 初始化一个虚拟头节点
        self.dummy = ListNode()

    def get(self, index):
        """ 获取指定下标的节点值 """
        curr = self.dummy.next
        for _ in range(index):
            if not curr:
                return -1
            curr = curr.next
        if curr:
            return curr.val
        return -1

    def addAtHead(self, val):
        """ 在头部添加节点 """
        new_node = ListNode(val, self.dummy.next)
        self.dummy.next = new_node

    def addAtTail(self, val):
        """ 在尾部添加节点 """
        curr = self.dummy
        while curr.next:
            curr = curr.next
        curr.next = ListNode(val)

    def addAtIndex(self, index, val):
        """ 在指定下标处添加节点 """
        prev = self.dummy
        for _ in range(index):
            if not prev.next:
                return
            prev = prev.next
        new_node = ListNode(val, prev.next)
        prev.next = new_node

    def deleteAtIndex(self, index):
        """ 删除指定下标的节点 """
        prev = self.dummy
        for _ in range(index):
            if not prev.next:
                return
            prev = prev.next
        if prev.next:
            prev.next = prev.next.next

# 测试用例
myLinkedList = MyLinkedList()
myLinkedList.addAtHead(1)
myLinkedList.addAtTail(3)
myLinkedList.addAtIndex(1, 2)
print(myLinkedList.get(1))  
myLinkedList.deleteAtIndex(1)
print(myLinkedList.get(1))

代码逻辑和方法：

ListNode 类定义了链表节点。
MyLinkedList 类中：
- __init__ 方法初始化一个虚拟头节点，方便操作。
- get 方法通过遍历到指定下标获取节点值，如果不存在则返回 -1。
- addAtHead 直接在虚拟头节点后添加新节点。
- addAtTail 遍历到尾部添加节点。
- addAtIndex 先找到要插入位置的前一个节点，然后插入新节点。
- deleteAtIndex 找到要删除节点的前一个节点，然后进行删除。

空间复杂度：主要是节点占用的空间，为 O(n)，其中 n 是节点数量。
时间复杂度：

get 最坏情况需要遍历整个链表，为 O(n)。
addAtHead、addAtTail、addAtIndex、deleteAtIndex 通常为 O(n)（找到特定位置的过程）。

206. 反转链表

简单

给你单链表的头节点 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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

1.以下是使用迭代方法反转链表的 Python 代码：

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

class Solution:
    def reverseList(self, head):
        """
        迭代反转链表
        """
        prev = None  # 前一个节点初始化为空
        curr = head  # 当前节点从头部开始

        while curr:  # 只要当前节点不为空
            next_node = curr.next  # 保存下一个节点
            curr.next = prev  # 当前节点的下一个指向改为前一个节点
            prev = curr  # 更新前一个节点为当前节点
            curr = next_node  # 移动到下一个节点
        return prev  # 最后返回反转后的头节点

# 测试用例
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

solution = Solution()
reversed_head = solution.reverseList(node1)

curr = reversed_head
while curr:
    print(curr.val, end=" ")
    curr = curr.next

以上代码逻辑和方法：通过不断改变节点的指向来实现反转。用两个指针 prev 和 curr，遍历链表时，先保存下一个节点，然后将当前节点的下一个指向改为前一个节点，再更新前一个节点和移动当前节点到下一个节点。

空间复杂度：只使用了固定的额外空间来存储几个指针，所以空间复杂度为 O(1)。

时间复杂度：遍历整个链表一次，时间复杂度为 O(n)。

2.以下是使用递归方法反转链表的 Python 代码：

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

class Solution:
    def reverseList(self, head):
        """
        递归反转链表
        """
        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  # 返回反转后的头节点

# 测试用例
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

solution = Solution()
reversed_head = solution.reverseList(node1)

curr = reversed_head
while curr:
    print(curr.val, end=" ")
    curr = curr.next

代码逻辑和方法：递归到链表末尾，然后从后往前依次改变节点指向。

空间复杂度：由于递归调用会使用栈空间，在最坏情况下，栈空间的使用与链表长度成正比，所以空间复杂度为 O(n)。

时间复杂度：也是 O(n)。