代码随想录算法训练营 Day 4
Published:
Q1. LeetCode 24
思路：使用虚拟头节点，将链表划分成多个子区间，每个区间长度为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:
temp = curr.next
temp1 = curr.next.next.next
curr.next = curr.next.next
curr.next.next = temp
curr.next.next.next = temp1
curr = curr.next.next
return dummy_head.next
难点
在进行交换时，注意链表会断开，因此需要用到临时变量ß
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q2. LeetCode 19
思路：
- 首先需要确定哪个节点为倒数第n个节点，因此让一个指针先走n步，然后另一个指针再从头出发。当第一个指针走到表尾时，第二个指针所指向的就是倒数第n个节点了
- 因为要删除倒数第n个节点，所以我们需要找到的是该节点的上一个节点，即倒数第n + 1个节点
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
slow, fast = dummy_head, dummy_head
while n:
fast = fast.next
n -= 1
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q3. LeetCode 160
解法1
思路：两个链表相交仅可能从较短的链表头节点开始。因此找到较长的链表，然后将其提前移动（两者长度的差值），最后同时移动且比较两个指针（非数值）是否相同
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
lenA = self.getLength(headA)
lenB = self.getLength(headB)
if lenA > lenB:
headA = self.moveForward(headA, lenA - lenB)
else:
headB = self.moveForward(headB, lenB - lenA)
while headA and headB:
if headA == headB:
return headB
headA = headA.next
headB = headB.next
def getLength(self, head):
l = 0
curr = head
while curr:
l += 1
curr = curr.next
return l
def moveForward(self, head, steps):
while steps:
head = head.next
steps -= 1
return head
解法2
思路：假如两个链表有相交节点并且长度相同，那么两个链表遍历到相交节点走过的步骤应该一样。因此可以使用等比例法
假如A中头节点到相交节点的距离为a，B中头节点到相交节点的距离为b，相交节点到尾节点的距离为c，那么遍历完A后从B的头节点重新开始，再次走到相交节点的距离为a+c+b，同理B的遍历采用相同方式，第二次走到相交节点的距离为b+c+a
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
currA = headA
currB = headB
while currA != currB:
currA = currA.next if currA else headB
currB = currB.next if currB else headA
return currA
复杂度分析
时间复杂度：O($n+m$) 空间复杂度：O(1)
Q4. LeetCode 142
找环的思路：快慢两个指针，快指针移动两步，慢指针移动一步，若有环，则两者必然会相遇
找环入口的思路：在上一步之后，将慢指针重新从头节点开始，两个指针现在每次都只移动一步，那么下次相遇节点就是环的入口
证明：文章链接
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)