算法工程师面试必考项——链表
共 10451字,需浏览 21分钟
·
2020-07-30 00:16
AI作者:田旭
AI编辑:田旭
1 知识点
1.1 什么是链表
提到链表,我们大家都不陌生,在平时的编码中我们也或多或少地使用过这个数据结构。算法(第4版) (豆瓣)一书中对链表的定义如下:
链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
1.2 链表结构
1.2.1 单向链表
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
1.2.2 双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接:一个指向前一个节点,(当此“连接”为第一个“连接”时,指向空值或者空列表);而另一个指向下一个节点,(当此“连接”为最后一个“连接”时,指向空值或者空列表)。
一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接
双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。
1.2.3 循环链表
在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的指针可以被称作访问指针。
用单向链表构建的循环链表
1.3链表相关的核心点
null/nil 异常处理 dummy node 哑巴节点 快慢指针 插入一个节点到排序链表 从一个链表中移除一个节点 翻转链表 合并两个链表 找到链表的中间节点
2 常见题型
83. 删除排序链表中的重复元素
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
思路:直接法,遇到重复就跳过
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
82. 删除排序链表中的重复元素 II
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
思路:定义哑节点指向链表头,定义双指针,一个指向当前节点,一个指向前一个节点。当有重复的元素时,cur指向下一位,直到下一位与当前节点不相等,用flag标记表示有重复数字,当循环完毕,pre的下一位指向cur的下一位,flag标记归位
当没有重复数字,pre指向cur
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next: # 空链表或单即节点链表
return head
dummy = ListNode(0) # 定义哑节点
dummy.next = head
pre = dummy # 哑节点指针
cur = head # 链表指针
flag = False # 标记是否重复
while cur:
while cur.next and pre.next.val == cur.next.val:
cur = cur.next # 将所有重复节点标记为True
flag = True
if flag is True: # 重复节点就跳过
pre.next = cur.next
flag = False
else:
pre = cur # 不重复就下一个节点
cur = cur.next
return dummy.next
206. 反转链表
反转一个单链表。
思路1:迭代,每次存储前一个节点,并让当前节点的next指针指向前一个节点
思路2:递归,假设我子节点下的所有节点都已经反转好了,现在就剩我和我的子节点没有完成最后的反转了,所以反转一下我和我的子节点。
# 迭代
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next # 存储节点的下一位
cur.next = pre # 指向前驱节点
pre = cur
cur = temp # cur指向原来的下一位
return pre
# 递归
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路:用双指针法,现将慢指针移动到要反转的部分的前一个节点,用另一个指针指向慢指针后面的节点,然后两两交换节点
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
dummy = ListNode(None)
dummy.next = head
pre = dummy
for i in range(1, m):
pre = pre.next # 前驱指针移动到位置m
cur = pre.next
for i in range(m, n): # 两两交换节点
temp = cur.next
cur.next = temp.next # cur一直不变,只修改指针到下一个位置
temp.next = pre.next # temp.next指向pre的next,也就是最新的第m个位置
pre.next = temp # 更新temp为最新的第m个位置
return pre
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:建立新链表,依次按升序链接两个链表的元素
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(None)
pre = dummy
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 if l1 else l2
return dummy.next
86. 分隔链表
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
思路:创建双链表,一个存储小于x的值,一个存储大于x的值
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
before = befornHead = ListNode(None)
after = afterHead = ListNode(None)
while head:
if head.val < x:
before.next = head
before = before.next
else:
after.next = head
after = after.next
head = head.next
after.next = None
before.next = afterHead.next
return befornHead.next
148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
思路:归并排序,找中点和合并操作
# 归并排序(递归),空间复杂度O(n)
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
h = res = ListNode(0)
while left and right:
if left.val < right.val:
h.next, left = left, left.next
else:
h.next, right = right, right.next
h = h.next
h.next = left if left else right
return res.next
# 快速排序
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None:
return head
# 分成三个链表,分别是比轴心数小,相等,大的数组成的链表
big = None
small = None
equal = None
cur = head
while cur:
temp = cur
cur = cur.next
if temp.val < head.val:
temp.next = small
small = temp
elif temp.val > head.val:
temp.next = big
big = temp
else:
temp.next = equal
equal = temp
# 拆完各自排序即可,equal 无需排序
big = self.sortList(big)
small = self.sortList(small)
ret = ListNode(None)
cur = ret
# 将三个链表组合成一起
# 可以同时返回链表的头指针和尾指针加速链表的合并。
for p in [small, equal, big]:
while p is not None:
cur.next = p
p = p.next
cur = cur.next
cur.next = None
return ret.next
143. 重排链表
给定一个单链表 L:L0→L1→…→L**n-1→Ln , 将其重新排列后变为:L0→Ln→L1→Ln-1→L2→Ln-2→…
思路:找到中点断开,翻转后面部分,然后合并前后两个链表
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return head
slow, fast = head, head
# 找到链表中点
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分
print(slow.next)
right = None
cur = slow.next
while cur:
temp = cur.next
cur.next = right
right = cur
cur = temp
# 将反转的后半部分插入到前半部分
left = head
while left and right:
slow.next = right.next
right.next = left.next
left.next = right
left = right.next
right = slow.next
141. 环形链表
给定一个链表,判断链表中是否有环。
思路1:哈希表,统计每个元素出现的次数
思路2:快慢指针,快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减 1
# 哈希表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
dic = {}
while head:
if head in dic:
return True
else:
dic[head] = 1
head = head.next
return False
# 快慢指针
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if head is None or head.next is None:
return False
slow = head
fast = slow.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
142. 环形链表 II
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回
null
。
思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while True:
if not (fast and fast.next):
return
slow = slow.next
fast = fast.next.next
if slow == fast:
break
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
138. 复制带随机指针的链表
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
思路:1、hash 表存储指针,2、复制节点跟在原节点后面
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return
dic = {}
dic[None] = None
cur = head
while cur:
if cur not in dic:
dic[cur] = Node(cur.val) # 将当前未拷贝的节点放入字典中
if cur.random not in dic:
dic[cur.random] = Node(cur.random.val) # 将当前未拷贝的random指针放入字典中
dic[cur].random = dic[cur.random]
if cur.next not in dic:
dic[cur.next] = Node(cur.next.val) # 将当前未拷贝的next指针放入字典中
dic[cur].next = dic[cur.next]
cur = cur.next
return dic[head]
234. 回文链表
请判断一个链表是否为回文链表。
思路1:将值复制到数组中,时间复杂度O(n),空间复杂度O(n)
思路2:快慢指针,先找到链表中点,然后反转后半部分,再与前半部分比较,时间复杂度O(n),空间复杂度O(1)
# 将值复制到数组中
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
visit = []
cur = head
while cur:
visit.append(cur.val)
cur = cur.next
return visit == visit[::-1]
# 找中点 -> 反转 -> 比较
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
pre = None
slow, fast = head, head
while fast and fast.next:
slow = slow.next # 使慢指针指向中间节点
fast = fast.next.next
while slow: # 反转后半部分,pre指向反转部分
temp = slow.next
slow.next = pre
pre = slow
slow = temp
while head and pre: # 比较两部分是否相同
if head.val != pre.val:
return False
head = head.next
pre = pre.next
return True
如果觉得不错,请关注一下公众号,也请为小编点个在看!
推荐阅读
机器学习算法工程师
一个用心的公众号