北大硕士LeetCode算法专题课--链表相关问题

ゝ一世哀愁。 2024-03-30 17:29 60阅读 0赞

**算法面试相关专题：**

[北大硕士LeetCode算法专题课-字符串相关问题\_][LeetCode_-]

[北大硕士LeetCode算法专题课-数组相关问题\_][LeetCode_- 1]

[北大硕士LeetCode算法专题课-基础算法查找\_][LeetCode_- 2]

[北大硕士LeetCode算法专题课-基础算法之排序\_][LeetCode_- 3]

[北大硕士LeetCode算法专题课---算法复杂度介绍\_][LeetCode_---]

[北大硕士LeetCode算法专题课-查找相关问题\_][LeetCode_- 4]

**链表的概****念**

**链表**（Linked list）是一种常见的基础数据结，是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构 【节点】， 按特定的顺序链接在一起的抽象数据类型。

链表中的元素称为节点(node)，每一个节点都有两个属性

l 一个用来记录当前节点中保存的数据

l 一个用来记录下一个节点的引用

![f09dfcc05dbd40fa93dfa70f41f7a093.png][]

链表是节点的集合。第一个节点（Node）一般被称为Head。最后一个节点的Next属性必须指向 None ，表明是链表的结尾

![1a5e16dd684746ff96cc39075a2e76cf.png][] **链表和数组的区****别**

在大多数编程语言中，链表和数组在内存中的存储方式存在明显差异。数组要求内存空间是连续的，链表可以不连续。 然而，在 Python 中，list是动态数组。所以在Python中列表和链表的内存使用非常相似。

链表和数组在以下的操作中也有本质区别：

l 插入元素：数组中插入元素时，插入位置之后的所有元素都需要往后移动一位，所以数组中插入元素最坏时间复杂度是 O(n)链表可以达到 O(1) 的时间复杂度

l 删除元素：数组需要将删除位置之后的元素全部往前移动一位，最坏时间复杂度是 O(n)链表可以达到 O(1) 的时间复杂度

l 随机访问元素：数组可以通过下标直接访问元素，时间复杂度为O(1)。链表需要从头结点开始遍历，时间复杂度为O(n)

l 获取长度： 数组获取长度的时间复杂度为O(1)，链表获取长度也只能从头开始遍历，时间复杂度为O(n)

**实现链****表**

先创建一个类，LinkedList

class LinkedList:
    def 	init 	(self):
    self.head = None

在LinkedList中，需要存储的唯一信息是链表的开始位置（链表的头部）。接下来，创建另一个类Node来表示链表的 每个节点：

class Node:
    def 	init 	(self, data):  self.data = data  self.next = None

我们可以给刚创建的两个类添加 repr 方法, 在创建实例的时候输出更多有用的信息

class LinkedList:
    def 	init 	(self):
    self.head = None
    
    def 	repr 	(self):  node = self.head  nodes = []
    while node is not None:  nodes.append(node.data)  node = node.next
    nodes.append("None")
    return " -> ".join(nodes)

class Node:
    def 	init 	(self, data):  self.data = data  self.next = None
    
    def 	repr 	(self):
    return self.data

创建测试类, 测试上面的代码

from LinkedList import LinkedList
    from Node import Node
    
    if  		name 	 == ' 	main 	':  llist = LinkedList()  print(llist)
    
    first_node = Node('a')  llist.head = first_node  print(llist)
    
    second_node = Node('b')  third_node = Node('c')  first_node.next = second_node  second_node.next = third_node  print(llist)

![ce02407cce6147b38235372aedaf2247.png][]

修改 init 方法，可以传入列表快速创建LinkedList

def 	init 	(self, nodes=None):
    self.head = None
    if nodes is not None:
    node = Node(data=nodes.pop(0))
    self.head = node
    for elem in nodes:
    node.next = Node(data=elem)  node = node.next

![651b053b9e2d4a4dbbd43a7417145ce5.png][]

**实现链表，添加节点**

在头部添加Node：在链表的开头添加一个Node，不必遍历链表，只需将新的Node的next属性指向 self.head ， 并将新的node设置为新的 self.head

![df697c667ad846b4913b9610aa79e60e.png][]

在尾部添加Node：必须遍历链表，与list不同，list可以直接获取长度， 链表只有从第一个Node，不断的去获取下一个Node 才能知道链表的尾部

def add_last(self, node):
    if self.head is None:  self.head = node  return
    for current_node in self:  pass
    current_node.next = node

![217adeb1ac7b40eca7120b97175c6cb5.png][]在指定元素后添加Node：遍历链表找到目标Node， 把目标Node的下一个元素， 赋值给要添加Node的next属性, 然后修改 目标Node的next属性, 指向新添加的Node, 当链表为空以及目标元素不存在时抛出异常

def add_after(self, target_node_data, new_node):
    if self.head is None:
    raise Exception("List is empty")
    
    for node in self:
    if node.data == target_node_data:  new_node.next = node.next  node.next = new_node
    return
    
    raise Exception("Node with data '%s' not found" % target_node_data)

在指定元素前添加Node：遍历链表找到目标Node，还需要记录当前节点的前一个节点。

def add_before(self, target_node_data, new_node):
    if self.head is None:
    raise Exception("List is empty")
    
    if self.head.data == target_node_data:
    return self.add_first(new_node)
    
    prev_node = self.head  for node in self:
    if node.data == target_node_data:  prev_node.next = new_node  new_node.next = node
    return
    prev_node = node
    
    raise Exception("Node with data '%s' not found" % target_node_data)

**实现链表，删除节****点**

删除Node：遍历链表找到目标Node，将目标Node的前一个Node的next属性,指向目标Node的next节点

def remove_node(self, target_node_data):
    if self.head is None:
    raise Exception("List is empty")
    
    if self.head.data == target_node_data:
    self.head = self.head.next  return
    
    previous_node = self.head  for node in self:
    if node.data == target_node_data:  previous_node.next = node.next  return
    previous_node = node
    
    raise Exception("Node with data '%s' not found" % target_node_data)

**其它常见链表介****绍**

刚才实现的是单链表，常见链表除了单链表之外还有双向链表以及循环链表

l 双向链表，顾名思义，Node中除了记录下一个元素（next）之外， 还通过一个属性记录上一个元素

![e8c2cf43092647d49a4cc18a7d26af30.png][]

刚才实现的是单链表，常见链表除了单链表之外还有双向链表以及循环链表

l 循环链表，将单链表中最后一个Node的next 属性, 指向头节点(head)，即为循环链表

![7f2da497e5304ae4b33d768ff809deb6.png][]**反转链表（LeetCode** **206）**

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

示例:

![dbbc97cc28aa45489439e3cb36c9e99a.png][]

![645a6ccdae9e4ac785ded592ce140efe.png][]

![ef36a742ed9649f68d160383cfce5879.png][]

**移除链表元素（****LeetCode** **203****）**

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点， 并返回 新的头节点 。

示例1:![8f5411a040fa4704b8c856b3a383ff44.png][]

由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next即为删除操作后的头节点。

def removeElements(head, val):  dummy_head = Node(0)  dummy_head.next = head  temp = dummy_head
    while temp.next:
    if temp.next.data == val:  temp.next = temp.next.next
    else:
    temp = temp.next
    return dummy_head.next

复杂度分析 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。 空间复杂度：O(1)

**两两交换链表中的节点（LeetCode** **24）**

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

示例 1：![221e8606286e474a849c02c9379c6cf2.png][]

![61d3e2ba1bab409587b60844024ad369.png][]

![272776ffaa614a7588809eee0d3980e8.png][]

**删除链表中的节点（LeetCode** **237）**

给请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只 能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

![be3f82577af2407fa7b401cfa1f72cd9.png][]

**删除链表中的节点（LeetCode** **237）**

思路分析：我们在做链表元素删除时， 一般的思路是，

① 找到要删除节点的上一个节点

② 将上一个节点的next属性 指向要删除节点的下一个节

![efd3d3012bce422b9f63b0dd679af387.png][]

但是，当前题目中的要求是， 我们无法访问头结点， 那么我们就无法得知要删除节点的上一个节点，但是我们能够获 取要删除节点的下一个节点， 利用它来完成我们的需求

\[4, 5,1, 9\] 链表，删除节点 5。既然要删除5， 我们把5的下一个节点的值付给它，然后删除下一个节点

![f14340acb4e74510925f65231bcd92b7.png][]

**删除链表中的倒数第N个节点（LeetCode** **19）**

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

![9f3d06121f5048ba87531bcb968e381f.png][]

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

输出：\[1,2,3,5\]

**删除链表中的倒数第N个节点（LeetCode** **19）**

思路： 首先遍历获取长度，创建一个虚拟头结点，从虚拟头结点开始遍历， L−n+1 个节点。当遍历到第 L−n+1个节 点时，它的下一个节点就是我们需要删除的节点

![be8dc0204c8642e8b34da55159da408f.png][]

def removeNthFromEnd(head, n):
    def getLength(head):  length = 0
    while head:
    length += 1
    head = head.next
    return length
    
    dummy = Node(0)  dummy.next = head
    length = getLength(head)  cur = dummy
    for i in range(1, length - n + 1):  cur = cur.next
    cur.next = cur.next.next
    return dummy.next

[LeetCode_-]: https://blog.csdn.net/JACK_SUJAVA/article/details/128642376
[LeetCode_- 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128626964
[LeetCode_- 2]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648
[LeetCode_- 3]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508
[LeetCode_---]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560
[LeetCode_- 4]: https://blog.csdn.net/JACK_SUJAVA/article/details/128643573?spm=1001.2014.3001.5501
[f09dfcc05dbd40fa93dfa70f41f7a093.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f834a20fb38c47d795c82e04c747cee2.png
[1a5e16dd684746ff96cc39075a2e76cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/72d2cac259674baead6364f810a4ec63.png
[ce02407cce6147b38235372aedaf2247.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c07bc2a3b7c3419388d3a23391a91179.png
[651b053b9e2d4a4dbbd43a7417145ce5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9016bf1d7a8f4b91913ce5f2ab2ab40f.png
[df697c667ad846b4913b9610aa79e60e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4f992c05c052448f9f56e8bd953ccf3c.png
[217adeb1ac7b40eca7120b97175c6cb5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1368798252ce4036a4e0f815f167a76e.png
[e8c2cf43092647d49a4cc18a7d26af30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3fe5d47b96ad48a682cec5b47f9281cc.png
[7f2da497e5304ae4b33d768ff809deb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/35ed8a812fb84f959e2b14e1dc1e1bf8.png
[dbbc97cc28aa45489439e3cb36c9e99a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/892ff393537441d19f7c45194187c47f.png
[645a6ccdae9e4ac785ded592ce140efe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/61035cb13e2f41628ed7c99ccf9ab55c.png
[ef36a742ed9649f68d160383cfce5879.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/cb1e69ac596a49c889a750478ace06ce.png
[8f5411a040fa4704b8c856b3a383ff44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/91db9a43645e479880b1b1e11578d7e4.png
[221e8606286e474a849c02c9379c6cf2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e82cf7c1d4d84cc79350eeec3a957e2d.png
[61d3e2ba1bab409587b60844024ad369.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/908daed1c9ed48418ec4ac36a43224e1.png
[272776ffaa614a7588809eee0d3980e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bcb06b5d1c25435990748e642af8d710.png
[be3f82577af2407fa7b401cfa1f72cd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a7762f40d9be4467ab124e99d8ad02eb.png
[efd3d3012bce422b9f63b0dd679af387.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d922303fe5e44901b6e5b54c72c1c414.png
[f14340acb4e74510925f65231bcd92b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/265f4569a2dd4aa0bef9358dd400e9fd.png
[9f3d06121f5048ba87531bcb968e381f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/39420300b3af460087d36a277d3084a3.png
[be8dc0204c8642e8b34da55159da408f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/390a6e8a464e458ea172a4a5198409c0.png