链表基础知识
链表的分类
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:648218d0-a2cf-4f41-ba77-e63a2f7de9e4
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:22902d61-7403-42ce-9726-11e67127af1f
单链表
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c2eb4401-c299-4f6b-bd06-e814dd7326e4
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:01664d23-eea6-4c0d-b97b-0885cf10901f
双向链表
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6dd9f7c5-cff8-428b-b64b-36f990d8c7a5
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6a9c9c0b-2e78-4b59-8ce2-288af49ca75a
单向循环链表
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6c26d1c5-6216-4a1e-ba83-bc19d4eb0801
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:903e333b-3799-4a28-b928-cb6992f0e317
双向循环链表
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b8c7a637-53ba-4885-97c2-b397f80433b0
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:289f6002-1ddb-4973-a313-76f4b13475ab
链表的定义
我们在刷LeetCode的时候，由于链表的节点都默认定义好了，直接用就行了，但是在面试的时候，一旦要手写链表代码时，节点的定义是大家容易犯错的地方，所有我们来看一下定义链表节点的方式。
#单链表
class ListNode(object):
def __init__(self, x):
#数据域
self.val = x
#指针域
self.next = None
链表的操作
单链表的删除操作
删除链表中的q节点，只需要执行p->next=q->next，即让p的指针域指向q的下一个节点。
向单链表中增加一个节点
在节点p后增加一个节点q，只需要执行q->next=p->next，p->next=q即可，这里一定要注意执行的先后顺序。如果先执行p->next=q，那么原链表的p->next的信息就丢失了。
解题有妙招
引入哑结点
哑结点也叫做哨兵节点，对于链表相关的题目，为了方便处理边界条件，一般我们都会引入哑结点来方便求解。首先我们来看一下什么是哑结点， 哑结点是指数据域为空，指针域指向链表头节点的节点，它是为了简化边界条件而引入的。下面我们来看一个具体的例子，例如要删除链表中的某个节点操作。 常见的删除链表的操作是找到要删元素的前一个元素，假如我们记为 pre。我们通过： pre->next=pre->next->next来执行删除操作。如果此时要删除的是链表的第一个结点呢？就不能执行这个操作了，因为链表的第一个结点的前一个节点不存在，为空。如果此时你设置了哑结点，那么第一个结点的前一个节点就是这个哑结点。这样如果你要删除链表中的任何一个节点，都可以通过pre->next=pre->next->next的方式来进行，这就简化的代码的逻辑。
双指针法
在求解链表相关的题目时，双指针也是非常常用的思想，例如对于求解链表有环问题时，我们申请两个指针，以一快一慢的速度在链表上行走，等他们相遇时，就可以知道链表是否有环；或者在求链表的倒数k个节点时，申请两个指针，一个指针先走k步，然后两个指针再同时向后移动，当先走的那个指针走到链表的末尾时，另一个指针恰好指向了倒数第k个节点。
该文档已经更新到github上了，https://github.com/meetalgo/meet_algo
反转链表
问题描述
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b7234d60-edc8-43ad-b68e-775b4d266323
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c001f9fe-7347-4179-9f98-233ba5f34cef
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e9a52905-4481-4685-95a3-b17ad94a87ee
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:30d90f45-fdd6-4aae-8f76-0cdf5e75b548
- 我们定义两个指针pre和cur。pre表示已反转部分的头结点，cur表示还没有反转部分的头结点。开始时cur=head，pre=None
- 每次让cur->next=pre，实现一次局部反转。
- 局部反转完成后，cur和pre同时向前移动一位。
- 循环上述过程，直到链表反转完成。
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverse(self, head):
cur = head
#初始化时，pre为None
pre = None
while cur:
next=cur.next
cur.next = pre
pre = cur
cur = next
return pre
head=ListNode(1,None)
cur=head
for i in range(2,6):
tmp=ListNode(i,None)
cur.next=tmp
cur=cur.next
s=Solution()
pre=s.reverse(head)
while pre!=None:
print(pre.val)
pre=pre.next
合并两个有序链表
问题描述
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:8861cbde-d4d6-4bb0-9f03-4ed7d3ae7c25
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:967ec9c7-077a-4a86-addf-83e5efa7ef78
示例：
输入: {1,3,5},{2,4,6}
返回值: {1,2,3,4,5,6}
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:37c3d299-72e7-4d38-9fe3-8deb037ce769
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:cdcbcca5-a3bc-4aed-a3d9-e2735eb2f762
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b1baead1-1cd2-4ab2-884a-d73624ee424c
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9f9137fb-6d8b-40d0-889e-26f260b37d4c
首先我们需要先创建一个哨兵节点，然后将prehead指向链表l1和l2中比较小的一个。如果相等的话，指向任意一个即可。然后将较小值对应的链表的指针后移一位。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:feb1504d-768d-4666-b759-6044d551db11
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ed108fcd-e48a-43c1-afa2-445c73ec2095
def mergeTwoLists(self, l1, l2):
#合并后链表的哨兵结点
head=ListNode(-1,None)
pre=head
#循环遍历，将两个链表中的较小值插入到合并后的链表中
while l1 and l2:
if l1.val <= l2.val: pre.next="l1" l1="l1.next" else: l2="l2.next" pre="pre.next" #将剩余的非空链表插入到合并链表的后面 if l1: return head.next < code></=>
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6caee306-4de9-4391-ac07-c4896971b9a2
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:de67108f-4f05-4789-96ee-4896f42eba17
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1, l2):
#链表l1为空，不需要合并，直接返回l2
if(l1==None):
return l2
#同理，l2为空，直接返回l1即可
if(l2==None):
return l1
if(l1.val<=l2.val): l1.next="self.mergeTwoLists(l1.next,l2)" return l1 else: l2.next="self.mergeTwoLists(l1,l2.next)" l2 < code></=l2.val):>
问题升级
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:46896f30-bf97-493b-9179-0d069a0e1a92
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:38cea994-fe26-4252-8b30-2f8eb51084e2
给定一个有序链表， 其中每个节点也表示有一个有序链表。结点包含两个类型的指针：
- 指向主链表中下一个结点的指针。
- 指向以此结点为头的链表。
示例如下所示：
4 -> 9 -> 15 -> 19
| | | |
7 13 18 28
| | |
8 21 37
|
20
实现函数flatten()，该函数用来将链表扁平化成单个链表。例如上面的链表，输出链表为
4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:2a62dc3d-b318-4983-a7d0-ed7eb4810af0
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9585116e-a19e-440e-9331-053b5456a3e2
4 -> 9
| |
7 13 旋转一下 4 -> 7 -> 8 -> 20
| ----------> |
8 9 -> 13
|
20
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:dbfc4d76-cc49-428c-a25b-7dc450dada74
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:75fdf9ce-592d-4091-abe1-236f8a3a237e
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:727f6738-0428-4dc6-be9c-aea9e8fa7dfc
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a0e35fc7-4fa0-47cc-b39b-95c74f697d9c
class ListNode:
def __init__(self, val=0, right=None, down=None):
self.val = val
self.right = right
self.down = down
class Solution:
def mergeTwoLists(self, l1, l2):
#如果有一个链表为空，则合并后的链表就是另外一个
if(l1==None):
return l2
if(l2==None):
return l1
if(l1.val<=l2.val): l1.down="self.mergeTwoLists(l1.down,l2)" return l1 else: l2.down="self.mergeTwoLists(l1,l2.down)" l2 def flatten(self,root): if root="=" none or root.right="=" none: #把root->right 看作是已经有序的单链表，
#然后通过递归来进行归并
return self.mergeTwoLists(root, self.flatten(root.right))
</=l2.val):>
链表中的节点每k个一组翻转
问题描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。你不能更改节点中的值，只能更改节点本身。
例如：
给定的链表是：1 -> 2 -> 3 -> 4 -> 5
对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5
对于 k=3， 你应该返回 3 -> 2 -> 1 -> 4 -> 5
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ee3241d0-bb3a-4a62-b6c3-8c02500626eb
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:586e30ae-9240-48f3-9fbf-2bd99566e1e0
- 我们首先将链表按照k个一组进行分组。对于最后一组，有可能元素个数不满足k个。
- 对于每一个分组，我们去判断元素的个数是否为k，如果是k的话，我们进行反转，否则不需要进行反转。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c5a01fd0-6c74-4c22-870c-a1546f56bf75
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ad1e9420-8b02-4031-97c3-4c40b5d111a1
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
#反转链表，并且返回链表头和尾
def reverse(self, head, tail):
prev = tail.next
p = head
while prev != tail:
next = p.next
p.next = prev
prev = p
p = next
return tail, head
def reverseKGroup(self, head, k):
#初始化一个哨兵节点，避免临界条件复杂的判断
prehead = ListNode(0)
#哨兵节点指向头结点
prehead.next = head
pre = prehead
while head:
tail = pre
#查看剩余部分长度是否大于等于k
for i in range(k):
tail = tail.next
#如果剩余长度小于k,则不需要反转，直接返回
if not tail:
return prehead.next
#tail指向子链表的尾部
#所以next指向下一个子链表的头部
next = tail.next
#将链表进行反转，并返回链表头和尾
head, tail = self.reverse(head, tail)
#把子链表重新接回原链表
pre.next = head
tail.next = next
pre = tail
head = tail.next
return prehead.next
判断链表是否有环
问题描述
给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
示例：
输入：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3
输出：true
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:47a26d92-2640-498d-99e0-40c9681b4430
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b3d94fdc-972f-4f83-ab4a-d9855fee9a21
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d006e5a6-acec-4184-8d2f-d34c968cea9a
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:edfa5389-5c9c-4e13-8da6-1271a40ec426
def hasCycle(self, head):
tags = set()
while head:
#表示已经被访问过了，代表有环
if head in tags:
return True
tags.add(head)
head = head.next
return False
我们可以知道该算法的时间复杂度和空间复杂度都是O(n)。那我们有更好的解法吗？
优化
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:abd6b194-6122-4278-a8c0-35ca0f3ca061
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:fcc1a092-aa60-444e-9983-cf0d60bf14b4
我们假设同学1以速度1在跑，同学2以速度2在跑。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6793e6a4-2440-43a1-818a-683eb9c6f036
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:49862b42-0b82-43a7-847d-e1b84de1dd72
def hasCycle(self, head):
#如果链表为空或者链表只有一个结点
#直接返回false,因为不可能有环
if not head or not head.next:
return False
#快慢指针
slow = fast = head
start = True
while slow != fast || start:
start=False
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
我们这里引入了一个变量start表示是否是起跑。
可以看到该算法的空间复杂度降低为O(1)。
链表中环的入口结点
问题描述
LeetCode 剑指 Offer II 022. 链表中环的入口节点
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a962b557-fe38-449d-ba08-8d1abcdb7fb9
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f471330c-f64e-4b20-92e0-61a9d4a34d50
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e70f0477-1c21-4c67-9e4e-61102e44a948
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e00901cc-7c21-41a5-b075-f32937417bb7
def EntryNodeOfLoop(self, pHead):
tags = set()
while pHead:
#表示已经被访问过了，代表有环
if pHead in tags:
return pHead
tags.add(pHead)
pHead = pHead.next
return None
我们可以看到该算法的时间复杂度和空间复杂度都是O(n)。
优化
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9958f253-25df-437c-8aa4-42363adad5d2
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:97f7910b-45b5-4661-b666-d9c19cc55db7
我们可以使用两个指针fast和slow。他们都从链表的头部开始出发，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。
我们假设链表中环外的长度为a，show指针进入环后又走了b的距离与fast相遇，此时fast指针已经绕着环走了n圈。所以快指针一共走了 a+n(b+c)+b=a+(n+1)b+nc的距离，我们知道快指针每次走2步，而慢指针每次走一步，所以，我们可以得出快指针走的距离是慢指针的两倍，即 a+(n+1)b+nc=2(a+b)，所以 a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的距离c，再加上n-1圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现slow和fast相遇时，我们再额外使用一个指针ptr指向链表头部，然后它和slow指针每次都向后移动一个位置。最终，他们会在入环点相遇。
Tips: 你也许会有疑问，为什么慢指针在第一圈没走完就会和快指针相遇呢？我们来看一下，首先，快指针会率先进入环内。然后，当慢指针到达环的入口时，快指针在环中的某个位置，我们假设此时快指针和慢指针的距离为x，若x=0，则表示在慢指针刚入环时就相遇了。我们假设环的长度为n，如果看成快指针去追赶慢指针，那么快指针需要追赶的距离为n-x。因为快指针每次都比慢指针多走一步，所以一共需要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的路程小于等于n，即走不完一圈就会相遇。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:8615c3a3-27dd-4e21-9102-0d6dac1c29a7
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f36c6309-12bf-40b6-8652-3294708c1b14
def detectCycle(head):
if not head:
return None
#快慢指针
slow = head
fast = head
while True:
if not fast or not fast.next:
return None
fast=fast.next.next
slow=slow.next
#相遇时，跳出循环
if fast == slow:
break
ptr = head
while ptr != slow:
ptr=ptr.next
slow=slow.next
return ptr
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
删除链表倒数第n个节点
问题描述
LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点
给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
分析问题
这个问题最简单的求解方式就是遍历一遍链表，获取到链表的长度m，然后求出倒数第n个结点的位置m-n+1，然后再遍历一次链表，找到第m-n+1的位置，删掉这个结点就好。其实，我们这里可以使用双指针法，只需要遍历一次链表就可以解决问题。
首先，我们可以设置两个指针slow和fast都指向头结点，然后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，我们通过slow.next=slow.next.next就可以把倒数第n个结点删掉。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:cfa8647c-1c97-4423-9636-a5b0da83d564
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b8c3fe9b-3493-42ff-a25f-3904ec63dec1
def removeNthFromEnd(self,head,n):
#左右指针指向头结点
slow = fast = head
#fast先走n步
while n>0 and fast:
fast = fast.next
n=n-1
if not fast:
return head.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head
该算法只遍历一遍链表，所以时间复杂度是O(n)，空间复杂度是O(1)。
两个链表的第一个公共结点
问题描述
LeetCode 剑指 Offer 52. 两个链表的第一个公共节点
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:47e029fe-7059-4d53-ad68-58fe736c0772
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1c6559dc-10bb-4709-a5e4-1cf1d79ff36a
要求：空间复杂度是O(1)，时间复杂度是O(m+n)。
示例：
分析问题
这个问题最直观的想法就是遍历链表headA，然后把headA中的所有每个节点都加入到集合中。然后再循环遍历链表headB，判断结点是否在集合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，继续遍历，直到结束。如果headB的所有结点都不在集合中，则表明不相交，直接返回null。
def getIntersectionNode(headA,headB):
nodes=set()
while headA:
nodes.add(headA)
headA=headA.next
while headB:
if nodes.__contains__(headB):
return headB
headB=headB.next
return None
该算法的时间复杂度是O(m+n)，空间复杂度是O(n)。其中m和n分别是链表headA和headB的长度。
由于题目要求时间复杂度是O(m+n)，空间复杂度是O(1)。我们这里可以使用双指针法将空间复杂度降低到O(1)。我们分别用两个指针p1和p2分别指向headA和headB，然后同时移动指针p1和p2。当p1到达headA的末尾时，让p1指向headB，当p2到达headB的末尾时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。
Tips:假设headA不相交的部分是a，headB不相交的部分是b，公共部分是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，可以知道p1和p2指针同时到达第一个公共结点；当a不等于b时，在p1移动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，然后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。
def getIntersectionNode(headA,headB):
p1 = headA
p2 = headB
while p1 != p2:
if p1:
p1=p1.next
else:
p1=headB
if p2:
p2=p2.next
else:
p2=headA
return p1
两个链表生成相加链表
问题描述
LeetCode 剑指 Offer II 025. 链表中的两数相加
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:554ca80b-b27d-4a08-a67a-8c7958a32dce
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a5303e04-7453-4c23-8527-a3c7f545d9ea
示例：
输入：[9,3,7]，[6,3]
返回值：{1,0,0,0}
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:cdcf07a7-4fcf-41d5-907f-f7c28aa7dfe9
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:60537c8b-0a99-4522-9cd4-526a93187384
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4584497a-d00f-4dfe-9bdd-9cbdb4ab8c3d
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4ab1bcce-3165-414c-8741-eed77cf72edf
- 将两个链表进行反转，然后直接求和。
- 借助栈这种先进后出的特性，来实现链表的右端对齐。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d63a84aa-33d0-4572-9a50-ac1b83f74018
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9c8e41b6-680e-452a-bf5c-cc40e728a1ba
class Solution(object):
def reverse(self, head):
cur = head
#初始化时，pre为None
pre = None
while cur:
next=cur.next
cur.next = pre
pre = cur
cur = next
return pre
def addTwoNumbers(self, l1, l2):
#将两个链表翻转
l1 = self.reverse(l1)
l2 = self.reverse(l2)
head=ListNode(0)
pre=head
#代表是否进位
carray=0
while l1 or l2:
v1=l1.val if l1 else 0
v2=l2.val if l2 else 0
sum=v1+v2+carray
#进位数
carray=int(sum/10)
tmp=sum%10
node=ListNode(tmp)
pre.next=node
pre=pre.next
if l1:
l1=l1.next
if l2:
l2=l2.next
if carray==1:
node=ListNode(carray)
pre.next=node
return self.reverse(head.next)
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f4f328ed-eb8e-4ce5-a2c3-beab3336198e
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:f0e02749-ebb7-44b7-a38d-5ad7cf710430
def addTwoNumbers(l1, l2):
#申请两个栈
stack1=[]
stack2=[]
#l1入栈
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
head = None
carry = 0
while stack1 and stack2:
num = stack1.pop() + stack2.pop() + carry
#求进位数
carry=int(num/10)
tmp=num%10
node = ListNode(tmp)
node.next = head
head = node
s = stack1 if stack1 else stack2
while s:
num = s.pop() + carry
carry = int(num / 10)
tmp = num % 10
node = ListNode(tmp)
node.next = head
head = node
if carry==1:
node = ListNode(carry)
node.next = head
head = node
return head
单链表的排序
问题描述
给定一个节点数为n的无序单链表，对其按升序排序。
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)。
示例：
输入：[-1,0,-2]
返回值：{-2,-1,0}
分析问题
由于题目要求时间复杂度是O(nlogn)，那时间复杂度是O(nlogn)的排序算法有归并排序、快速排序和堆排序，其中最适合链表的排序算法是归并排序。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b793158a-0674-462d-bb9b-72cd3648b5b9
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:19398552-2e8f-4b2e-bbea-0f3b1ccf667d
- 分割环节
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针法，快指针每次移动2步，慢指针每次移动1步，当快指针走到链表的末尾时，慢指针恰好指向了链表的中点位置。
- 找到中点后，将链表在中点处分割成两个子链表。
- 然后递归的进行分割，直到分割后的链表只有一个节点或者为Null。这时，分割的子链表都是有序的，因为只包含一个节点。
- 合并环节
- 将两个有序的链表合并成一个有序链表。我们可以采用双指针法求解。
- 递归执行，直到合并完成。
class Solution:
def sortList(self, head):
#如果链表为空或者只包含一个节点，递归终止
if not head or not head.next:
return head
#使用快慢指针法来寻找链表的中点
slow=head
fast=head.next
while fast and fast.next:
fast=fast.next.next
slow=slow.next
#slow指向的就是链表的中点，将链表在中点处进行分割
head2=slow.next
slow.next=None
#递归的切割分割链表
left = self.sortList(head)
right = self.sortList(head2)
#合并链表，使用双指针法
tmp = res = ListNode(0)
while left and right:
if left.val < right.val:
tmp.next=left
left=left.next
else:
tmp.next=right
right=right.next
tmp=tmp.next
if left:
tmp.next=left
else:
tmp.next=right
return res.next
该算法的时间复杂度是O(n)。由于自顶向下是通过递归来实现的，如果考虑递归调用栈的栈空间，那么该算法的空间复杂度是O(logn)。
优化
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:cec3d7b9-2cd3-4cbd-a02d-7bff1136164c
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:354acc30-50d3-4511-acbd-8f0070e3b28f
首先，我们求出链表的长度length。然后将链表拆分成子链表进行合并。
- 我们用sublength表示每次需要排序的子链表的长度，初始时sublength=1。
- 每次将链表拆分成若干个长度为sublength的子链表（最后一个子链表的长度可能小于sublength），按照每两个子链表一组进行合并，合并后即可以得到若干个长度为sublength * 2的有序子链表（最后一个子链表的长度可能小于sublength * 2）。
- 将sublength的值加倍，重复第二步，然后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就完成了。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:eaf4add6-7401-4eca-a608-bcddde8e35c2
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:df182d5e-25ed-4a9a-962a-a51f4b0efb95
class Solution:
def sortList(self, head):
#合并两个有序链表
def merge(head1, head2):
#哨兵节点
dummyHead = ListNode(0)
temp=dummyHead
while head1 and head2:
if head1.val <= 2 head2.val: temp.next="head1" head1="head1.next" else: head2="head2.next" temp="temp.next" if head1: return dummyhead.next #如果链表为空，直接返回 not head: head #遍历一遍链表，求出链表的长度 length="0" node="head" while node: +="1" #创建一个哨兵节点,指向链表头 dummyhead="ListNode(0)" #初始时，子链表的长度为1 sublength="1" < length: prev="dummyHead" cur="dummyHead.next" cur: #截取长度为sublength的子链表head1 for i in range(1, sublength): cur.next: break cur.next="None" #截取长度为sublength的子链表head2 and #截取完后剩余的链表节点 surplus_head="None" #将两个有序链表进行合并 merged="merge(head1," head2) #将排好序的链表插入到新生成的链表里 prev.next="merged" #将指针移动到链表的末尾 prev.next: #继续合并剩余的节点 * code></=>
该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。
判断一个链表是否为回文结构
问题描述
LeetCode 剑指 Offer II 027. 回文链表
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:21247704-e361-4718-92f5-c659826adaae
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:45b34077-55fd-4731-83a0-6733e4a8d3bf
示例：
输入：{1,2,2,1}
输出：true
说明：1 -> 2 -> 2 -> 1
分析问题
回文串是指正读反读都一样的字符串，最简单的是使用双指针法。但是对于链表这种数据结构来说，指针只能向一个方向移动，也就是说只能找到后继节点，没办法找到前驱节点。所以没办法使用双指针法，要想使用双指针，我们就需要把链表元素放入一个数组中，然后再去判断是否是回文，这需要O（n）的空间复杂度，这里就不在赘述。大家可以去看第44题。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c66e6add-baec-41b4-a79e-3b8da39366dd
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:260c8b76-0256-4531-beeb-fa57cd909bcf
- 快慢指针寻找链表中点。
- 对链表的后半部分进行翻转
- 前半部分和后半部分进行比较。
class Solution:
def isPalindrome(self, head) -> bool:
#链表为空，直接返回true
if head is None:
return True
#找到链表的中点
middle_point = self.middle_point(head)
second_start = self.reverse_list(middle_point.next)
#判断前半部分和后半部分是否相等
result = True
first = head
second = second_start
while result and second is not None:
if first.val != second.val:
result = False
first = first.next
second = second.next
#还原链表并返回结果
middle_point.next = self.reverse_list(second_start)
return result
#快慢指针寻找中点
def middle_point(self, head):
fast = head
slow = head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow
#翻转链表
def reverse_list(self, head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
链表内指定区间反转
问题描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left
Original: https://www.cnblogs.com/cxyxz/p/15509340.html
Author: 算法推荐管
Title: 学习链表复盘中
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/562445/
转载文章受原作者版权保护。转载请注明原作者出处！