当前位置: 首页> 文旅> 美景 > 二、链表(2)

二、链表(2)

时间:2025/7/11 7:32:16来源:https://blog.csdn.net/weixin_49206002/article/details/140609631 浏览次数:0次

24. 两两交换链表中的节点
法一:迭代,while循环,注意要获取next给变量,得先判断非null,
需要4个变量, n0是前,n1 n2是交换的两,n3是n2的下一个可能为空,这种先把变量保存起来,动链表的时候就不会丢啦

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dum = ListNode(next = head)n0 = dum# 迭代,需要3个变量while n0.next and n0.next.next:n1 = n0.nextn2 = n1.nextn3 = n2.next  # 可nulln0.next = n2n2.next = n1n1.next = n3n0 = n1return dum.next

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

法二:递归,三个变量,每次返回头节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:# 递归# 终止条件 head or head head.next == nullif head is None or head.next is None:return head# 3个变量n1 = headn2 = n1.nextn3 = n2.next n2.next = n1n1.next = self.swapPairs(n3)return n2

19.删除链表的倒数第N个节点
快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:# 删除节点,需要找到前面一个节点# 但凡考虑头节点特殊情况,加dum虚拟哨兵节点fast = slow = dum = ListNode(next=head)for _ in range(n):fast = fast.nextwhile fast.next:slow = slow.nextfast = fast.nextt = slow.nextslow.next = t.nextt.next = Nonereturn dum.next

时间复杂度:O(n) 只需要一次循环
空间复杂度:O(1)

面试题 02.07. 链表相交
法一:双指针
时间复杂度:O(n)
空间复杂度:O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:curA = dumA = ListNode(next = headA)curB = dumB = ListNode(next = headB)cntA = 0cntB = 0while curA.next:curA = curA.nextcntA += 1while curB.next:curB = curB.nextcntB += 1curA = dumAcurB = dumBif cntA - cntB > 0:for _ in range(cntA - cntB):curA = curA.nextelse:for _ in range(cntB - cntA):curB = curB.nextwhile curA.next != curB.next and curA.next != None:curA = curA.nextcurB = curB.nextreturn curA.next# return curA.next if curA.next != None else None

在这里插入图片描述

法二:
相交部分长度c,走完a,再走一段b-c,就到了相交的head,对于b,走完b再走一段a-c,也到了相交的head,两个走的长度都一样,如果==就返回,(这个可能是Head也可能没有相交就纯None。
自问:什么时候相遇?

class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:A = headAB = headBwhile A != B:A = A.next if A != None else headBB = B.next if B != None else headAreturn A

相等时有两个情况,到了相交的节点 or 没有相交都是None
142.环形链表II
快慢指针
快指针速度是慢指针的两倍,环长为b,前面直的部分长度为a,当慢指针到达入环的节点时,(走了一段直a)快指针的路径是他的两倍,(在环里走了a),实。接下来他们的速度差还是两倍,快的在前面,慢的在后面,两个的距离越来越大,慢的看做静止,快的相对于慢的走b-a次就能追上慢的,此时慢的也走了b-a次。这是快慢指针的第一次相遇。慢指针再走a次就能到达环的入口,再来第三个指针从head开始和慢指针同速前进,就会在head第二次相遇

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:fast = headwhile fast != slow:fast = fast.nextslow = slow.nextreturn fastreturn

在这里插入图片描述
注意
slow = fast = res = ListNode(next = head)
while fast != slow: # 这么写while不会执行

法二:集合法
set:无序不重复,可以看在不在

版本二)集合法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:visited = set()while head:if head in visited:return headvisited.add(head)head = head.nextreturn None
关键字:二、链表(2)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: