首页 > 编程语言 >【算法】链表

【算法】链表

时间：2023-09-23 11:56:22浏览次数：47  
标签：head self next 链表 算法 节点 指针

1 链表理论基础

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

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

1.1 链表的类型

  1. 单链表：指针域只能指向下一个节点。
  2. 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。因此，双链表既可以向前查询也可以向后查询。

  3. 循环链表：链表首尾相连，可以用来解决约瑟夫环问题。

1.2 链表的定义

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

1.3 链表的操作

  • 删除节点

  • 添加节点

1.4 性能分析

2 移除链表元素

题目：给你一个链表的头节点 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
输出：[]

思路

如果删除的是头结点该怎么办呢？

  • 直接使用原来的链表来进行删除操作

只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点；但因为在单链表中移除头结点和移除其他节点的操作方式不一样，需要单独写一段逻辑来处理移除头结点的情况。

  • 设置一个虚拟头结点在进行删除操作

可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(next = head) # 创建虚拟头部节点以简化删除过程       
        curr = dummy_head
        while curr.next: # 遍历列表并删除值为val的节点
            if curr.next.val == val: # 下一个节点为val
                curr.next = curr.next.next
            else:
                curr = curr.next

    return dummy_head.next

3 设计链表

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

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

思路

实现单向链表，即每个节点仅存储本身的值和后继节点。除此之外，我们还需要一个虚拟节点作为头节点，和一个 size 参数保存有效节点数。如下图所示。

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
    curr = self.dummy_head.next
    for i in range(index):
            curr = curr.next
    return curr.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:
    curr = self.dummy_head
    while curr.next:
        curr = curr.next
    curr.next = ListNode(val)
    self.size += 1

def addAtIndex(self, index: int, val: int) -> None:
    if index < 0 or index > self.size:
        return
    curr = self.dummy_head
    for i in range(index):
        curr = curr.next
    curr.next = ListNode(val, curr.next)
    self.size += 1

def deleteAtIndex(self, index: int) -> None:
    if index < 0 or index >= self.size:
        return
    curr = self.dummy_head
    for i in range(index):
        curr = curr.next
    curr.next = curr.next.next
    self.size -= 1



Your MyLinkedList object will be instantiated and called as such:


obj = MyLinkedList()


param_1 = obj.get(index)


obj.addAtHead(val)


obj.addAtTail(val)


obj.addAtIndex(index,val)


obj.deleteAtIndex(index)

4 反转链表

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

示例 1：

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

示例 2：

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

提示：

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

思路

只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示：

  1. 双指针法
    2. class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head   
        pre = None
        while cur:
            temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur.next = pre # 反转
            # 更新pre、cur指针
            pre = cur
            cur = temp
        return pre

    时间复杂度: O(n)，空间复杂度: O(1)

  2. 递归法
    3. 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)

    时间复杂度: O(n)，空间复杂度: O(n)

5 两两交换链表中的节点

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。

示例 1：

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

示例 2：

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

示例 3：

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

思路

  1. 虚拟头节点

    2. class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(next = head)
        curr = dummy_head

        while curr.next and curr.next.next:
        first = curr.next
        second = first.next
        tmp = second.next
        
        curr.next = second
        second.next = first
        first.next = tmp

        curr = first
    
    return dummy_head.next

    时间复杂度：O(n)，空间复杂度：O(1)

  2. 递归法
    3. class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        first = head
    second = head.next
    next = second.next

    second.next = first
    first.next = self.swapPairs(next)  # 将以next为head的后续链表两两交换

    return second

    时间复杂度：O(n)，空间复杂度：O(1)

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

题目：给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

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

思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(next = head)
        fast = slow = dummy_head
        for i in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next

时间复杂度: O(n)，空间复杂度: O(1)

7 链表相交

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路

简单来说，就是求两个链表交点节点的指针。注意，交点不是数值相等，而是指针相等。如果有交点，那么右端必定共享相同节点指针。可以求出两个链表的长度并求差值，然后让curA移动到和curB 末尾对齐的位置（即右对齐）。

此时就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

class Solution:
    def get_size(self, head: ListNode) -> int:
        size = 0
        while head:
            head = head.next
            size += 1
        return size

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -&gt; ListNode:
    # 如果相交，右对齐后从右往左必定有相同元素
    lenA = self.get_size(headA)
    lenB = self.get_size(headB)
    currA, currB = headA, headB
    # 保证A是最长链表
    if lenB &gt; lenA:
        lenA, lenB = lenB, lenA
        currA, currB = currB, currA
    # 右对齐
    diff = lenA - lenB
    for _ in range(diff):
        currA = currA.next 
    
    while currA: #  遍历curA 和 curB，遇到相同则直接返回
        if currA == currB: 
            return currA
        currA = currA.next
        currB = currB.next
			return None

8 环形链表**

题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

示例 2：

输入：head = [1], pos = -1
输出：返回 null

思路

  1. 快慢指针法

    2. 主要考察两个知识点：

    • 判断链表是否有环
    • 如果有环，如何找到这个环的入口

    判断链表是否有环

    使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

    如果有环，如何找到这个环的入口**

    假设从头结点到环形入口节点的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点的节点数为y。 从相遇节点再到环形入口节点节点数为 z。 如图所示：

     

     

    那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数。

    因为fast指针一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：(x + y) * 2 = x + y + n (y + z)

    要找环形的入口，那么要求的是x：x = n (y + z) - y ,

    再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

    拿n为1的情况举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。此时公式化解为 x = z，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是环形入口的节点。

    n如果大于1，就是fast指针在环形转n圈之后才遇到 slow指针。这种情况和n为1的时候效果是一样的，只不过index1 指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

    class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head

        while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
      
        # If there is a cycle, the slow and fast pointers will eventually meet
        if slow == fast:
            # Move one of the pointers back to the start of the list
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    # If there is no cycle, return None
    return None

    时间复杂度: O(n)，空间复杂度: O(1)

  2. 集合法
    3. class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()

        while head:
        if head in visited:
            return head
        visited.add(head)
        head = head.next
    
    return None

标签：head,self,next,链表,算法,节点,指针
From： https://www.cnblogs.com/Aikoin/p/17724078.html

相关文章

  • 代码随想录算法训练营-动态规划-1|509. 斐波那契数、70. 爬楼梯
    509. 斐波那契数 1classSolution:2deffib(self,n:int)->int:3ifn<=2:4returnn56prev1,prev2=0,17for_inrange(2,n+1):8sum_value=prev1+prev29prev1,......
  • 【算法】数组
    1数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的数组内存空间的地址是连续的在删除或者增添元素时，需要移动其他元素的地址：C++要注意vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。数组的元素是不能......
  • 代码随想录算法训练营day17 | ● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.
    110.平衡二叉树classSolution{public:intgetHeight(TreeNode*node){if(node==NULL)return0;intleftHeight=getHeight(node->left);if(leftHeight==-1)return-1;intrightHeigh......
  • LZW字典压缩算法及例程
    字典压缩算法是一种数据压缩方法，其基本原理是将重复出现的字符串或者片段用一个短的代表符号来表示，从而减小数据的存储空间。字典压缩算法通常用于无损压缩数据。一种常见的字典压缩算法是Lempel-Ziv-Welch(LZW)算法。该算法通过构建和更新一个字典来实现压缩。初始时，字典中包含......
  • 【算法】算法性能分析
    1时间复杂度1.1知识点时间复杂度是一个函数，它定性描述该算法的运行时间。通常会估算算法的操作单元数量来代表程序消耗的时间。假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复......
  • 【POJ 1521】Entropy 题解（贪心算法+优先队列+哈夫曼树）
    熵编码器是一种数据编码方法，通过对删除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。换句话说，熵编码去除了最初不需要的信息，以准确编码消息。高度的熵意味着一条消息包含大量浪费的信息；以ASCII编码的英文文本是具有极高熵的消息类型的示例。已经压缩的消息，如JPEG图......
  • 数据结构之 - 链表数据结构详解: 从基础到实现
    链表（LinkedList）是计算机科学中常用的数据结构之一，它具有灵活的内存分配和高效的插入、删除操作。本文将深入介绍链表的特性、基本类型、操作以及在实际应用中的使用场景。1.什么是链表？链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用（或指针）。与数......
  • Kafka消息压缩算法性能调优与选择
    前言Kafka作为一款高性能的分布式消息队列，其消息压缩算法的选择和调优对于系统性能的提升至关重要。本文将深入探讨Kafka消息压缩算法的性能调优和选择。压缩算法的选择Kafka支持多种压缩算法，包括gzip、snappy和lz4。这些算法各有优缺点，需要根据实际情况进行选择。gzipgzip是......
  • 算法训练day17 LeetCode 110
    算法训练day17LeetCode110.257.404110平衡二叉树题目110.平衡二叉树-力扣（LeetCode）题解代码随想录(programmercarl.com)当子树已经不平衡，直接返回-1.平衡则返回子数高度进行更高树间的高度比较classSolution{public:intgetHeight(TreeNode*node)......
  • 拓展欧几里得算法揭秘
    最大公约数更相减损术：\(\gcd(x,y)=\gcd(y-x,x)(x\leqy)\)。设\(\gcd(x,y)=k,\gcd(p,q)=1,x=kp,y=kq\)。那么\(\gcd(y-x,x)=\gcd(kq-kp,kp)=k\times\gcd(q-p,p)\)。设\(\gcd(q-p,p)=r,q-p=rb,p=ra\)。那么\(q=r(a+b)\)。因为\(\gcd(p,q)=1=\gcd(ra,r(a+b))\)。所以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99