leetcode | 链表

程序员文章站 2022-05-06 20:37:48

...

理论部分

一、什么是链表？

1.和数组一样，链表也是一种线性表。

2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。

3.链表中的每一个内存块被称为节点 Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

二、为什么使用链表？即链表的特点

1.插入、删除数据效率高 O(1) 级别（只需更改指针指向即可），随机访问效率低 O(n) 级别（需要从链头至链尾进行遍历）。

2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

三、常用链表：单链表、循环链表和双向链表

1.单链表

每个节点只包含一个指针，即后继指针。
单链表有两个特殊的节点，即首节点和尾节点。

为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址 null。
性能特点：插入和删除节点的时间复杂度为 O(1)，查找的时间复杂度为 O(n)。

2.循环链表

除了尾节点的后继指针指向首节点的地址外均与单链表一致。
适用于存储有循环特点的数据，比如约瑟夫问题。

3.双向链表

节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针 prev）和下一个节点地址（后继指针 next）。
首节点的前驱指针 prev 和尾节点的后继指针均指向空地址。
性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高 O(1) 级别。

以删除操作为例，删除操作分为 2 种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为 O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到 p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置 p，每一次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表

首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

四、选择数组还是链表？

4.1 插入、删除和随机访问的时间复杂度

数组：插入、删除的时间复杂度是 O(n)，随机访问的时间复杂度是 O(1)。
链表：插入、删除的时间复杂度是 O(1)，随机访问的时间复杂端是 O(n)。

4.2 数组缺点

若申请内存空间很大，比如 100M，但若内存空间没有 100M 的连续空间时，则会申请失败，尽管内存可用空间超过 100M。
大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

4.3 链表缺点

内存空间消耗更大，因为需要额外的空间存储指针信息。
对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的 GC（自动垃圾回收器）操作。

4.4 如何选择？

数组简单易用，在实现上使用连续的内存空间，可以借助 CPU 的缓冲机制预读数组中的数据，所以访问效率更高
链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法预读。
如果代码对内存的使用非常苛刻，那数组就更适合。

五、如何优雅的写出链表代码？6大学习技巧

5.1 理解指针或引用的含义

含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
示例：
p—>next = q; 表示 p 节点的后继指针存储了 q 节点的内存地址。
p—>next = p—>next—>next; 表示 p 节点的后继指针存储了 p 节点的下下个节点的内存地址。

5.2 警惕指针丢失和内存泄漏（单链表）

1.插入节点
在节点 a 和节点 b 之间插入节点 x，b 是 a 的下一节点，p 指针指向节点 a，则造成指针丢失和内存泄漏的代码：p—>next = x; x—>next = p—>next; 显然这会导致 x 节点的后继指针指向自身。
正确的写法是两句代码交换顺序，即：x—>next = p—>next; p—>next = x;

2.删除节点
在节点 a 和节点 b 之间删除节点 b，b 是 a 的下一节点，p 指针指向节点 a：p—>next = p—>next—>next;

5.3 利用“哨兵”简化实现难度

1.什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。

2.未引入“哨兵”的情况
如果在 p 节点后插入一个节点，只需 2 行代码即可搞定：

new_node—>next = p—>next;
p—>next = new_node;

但，若向空链表中插入一个节点，则代码如下：

if(head == null){
head = new_node;
}

如果要删除节点 p 的后继节点，只需 1 行代码即可搞定：
p—>next = p—>next—>next;
但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：

3.引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。

5.4 重点留意边界条件处理

经常用来检查链表是否正确的边界 4 个边界条件：

如果链表为空时，代码是否能正常工作？
如果链表只包含一个节点时，代码是否能正常工作？
如果链表只包含两个节点时，代码是否能正常工作？
代码逻辑在处理头尾节点时是否能正常工作？

5.5 举例画图，辅助思考

核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

比如往单链表中插入一个数据这样一个操作，画图如下：

leetcode | 链表

5.6 多写多练，没有捷径

5 个常见的链表操作：

单链表反转
链表中环的检测
两个有序链表合并
删除链表倒数第 n 个节点
求链表的中间节点

代码部分

1. 合并两个有序链表

leetcode 21：https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码：

# 定义一个Node类
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummy = pre = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next
        pre.next = l1 or l2
        return dummy.next

执行结果：
leetcode | 链表

2. 删除链表的倒数第N个节点

leetcode 19：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

代码：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if head == None:
            return None
        first = head
        second = head
        for i in range(n):
            first = first.next
            if first == None:
                return second.next
        while first.next != None:
            first = first.next
            second = second.next
        if(n == 1):
            second.next = None
        else:
            second.next = second.next.next
        return head

执行结果：
leetcode | 链表

3. 旋转链表

leetcode 61：https://leetcode-cn.com/problems/rotate-list/

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL

解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL

解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思路：

求出链表的长度 len
k = k % len 取余就是我们要右移的距离。
找到倒数第 k 个位置。可以使用双指针法。
记录慢指针的 next 节点，这就是最后要返回的节点。

代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # 求出链表的长度
        if (head == None or k == 0):
            return head
        first = head
        len = 0
        while first != None:
            first = first.next
            len += 1
        k = k % len
        if k == 0:
            return head
        first = head
        second = head
        while k > 0:
            k -= 1
            first = first.next
        while first.next != None:
            first = first.next
            second = second.next
        res = second.next
        second.next = None
        first.next = head
        return res

执行结果：
leetcode | 链表

欢迎关注微信公众号 shinerise，与你一起慢慢进步~

leetcode | 链表

相关标签： leetcode 链表指针数据结构

上一篇：用Spring Boot+Vue做微人事项目第二天

下一篇： ssm整合无法注入dao层

leetcode | 链表

理论部分

一、什么是链表？

二、为什么使用链表？即链表的特点

三、常用链表：单链表、循环链表和双向链表

1.单链表

2.循环链表

3.双向链表

4.双向循环链表

四、选择数组还是链表？

4.1 插入、删除和随机访问的时间复杂度

4.2 数组缺点

4.3 链表缺点

4.4 如何选择？

五、如何优雅的写出链表代码？6大学习技巧

5.1 理解指针或引用的含义

5.2 警惕指针丢失和内存泄漏（单链表）

5.3 利用“哨兵”简化实现难度

5.4 重点留意边界条件处理

5.5 举例画图，辅助思考

5.6 多写多练，没有捷径

代码部分

1. 合并两个有序链表

2. 删除链表的倒数第N个节点

3. 旋转链表

欢迎关注微信公众号 shinerise，与你一起慢慢进步~

Java之链表实现栈结构

Java之使用链表实现队列

23. 合并K个排序链表

Python单链表简单实现代码

python数据结构之单向非循环链表

#leetcode刷题之路48-旋转图像

#leetcode刷题之路46-全排列

LeetCode刷题第二天

#leetcode刷题之路45-跳跃游戏 II

python(leetcode)-1.两数之和