代码随想录算法训练营第四天
24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例
输入：head = [1,2,3,4]
输出：[2,1,4,3]
思路
- 交换节点的值，而非交换节点指针
- 涉及两个指针，我们用cur和cur.next表示，每次走两步
- while循环条件：cur and cur.next非空
代码
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @Time : 2022.10
# @Author : hello algorithm!
# @Note : https://leetcode.cn/problems/swap-nodes-in-pairs/
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""
交换节点val，并不是交换节点
"""
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
temp_node = cur.next
temp_val = temp_node.val
temp_node.val = cur.val
cur.val = temp_val
cur = temp_node.next
return head
if __name__ == '__main__':
pass
19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例
、
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路
- 本题采用快慢指针（slow和fast指针）方法进行解题
- 题目中给出了n的有效性，因此不需要判断；当链表长度为1时，n=1时，此时删除头节点，比较费劲，因此采用虚拟头节点方法
- slow和fast指针同时指向dummy_head节点，先让fast走n+1步，然后同时移动slow和fast指针，直到fast指针为None，此时进行节点删除操作
代码
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @Time : 2022.10
# @Author : hello algorithm!
# @Note : https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""
本题采用快慢指针方法进行解题，题目中给出了n的有效性，因此不需要判断；当链表长度为1时，n=1时，此时删除头节点，比较费劲，
因此采用虚拟头节点方法：
slow和fast指针同时指向dummy_head节点，先让fast走n+1步，然后同时移动slow和fast指针，直到fast指针为None，
此时进行节点删除操作
"""
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_head = ListNode()
dummy_head.next = head
slow = dummy_head
fast = dummy_head
for i in range(n + 1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_head.next
if __name__ == '__main__':
pass
02.07.链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
示例
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
思路
- 快慢指针，比较节点相等，而非节点数值
- 先计算出两个链表的长度，使用快慢指针，根据长度差，分别指向长度长的head和长度短的head，先让快指针移动长度差次，然后快慢指针同时移动，比较两个节点，相等则直接返回，遍历到最后不相等，则返回None
代码
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @Time : 2022.10
# @Author : hello algorithm!
# @Note : https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
"""
先计算出两个链表的长度，使用快慢指针，根据长度差，分别指向长度长的head和长度短的head，
先让快指针移动长度差次，然后快慢指针同时移动，比较两个节点，相等则直接返回，遍历到最后
不相等，则返回None
"""
def getListLength(self, head: ListNode) -> int:
cur = head
length = 0
while cur:
length += 1
cur = cur.next
return length
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
length_a = self.getListLength(headA)
length_b = self.getListLength(headB)
diff = abs(length_b - length_a)
long_cur = headA
short_cur = headB
if length_b > length_a:
long_cur = headB
short_cur = headA
while diff:
long_cur = long_cur.next
diff -= 1
while long_cur:
if long_cur == short_cur:
return long_cur
long_cur = long_cur.next
short_cur = short_cur.next
return None
if __name__ == '__main__':
pass
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
思路
- 快慢指针，fast和slow指针同时指向head节点，fast指针每次走2步，slow指针每次走1步；
- 当fast和slow指针在环中相遇时，将cur指针指向head，cur和slow指针每次走1步，当两个指针相遇时，即为换环的入口。不知道为啥，提交代码，需要把ListNode的定义去掉…
代码
# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @Time : 2022.10
# @Author : hello algorithm!
# @Note : https://leetcode.cn/problems/linked-list-cycle-ii/
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""
fast和slow指针同时指向head节点，fast指针每次走2步，slow指针每次走1步，当fast和slow指针在环中
相遇时，将cur指针指向head，cur和slow指针每次走1步，当两个指针相遇时，即为换环的入口
不知道为啥，提交代码，需要把ListNode的定义去掉......
"""
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
cur = head
while cur != slow:
cur = cur.next
slow = slow.next
return cur
return None
if __name__ == '__main__':
head = ListNode(3)
l2 = ListNode(2)
l3 = ListNode(0)
l4 = ListNode(-4)
head.next = l2
l2.next = l3
l3.next = l4
l4.next = l2
s = Solution()
s.detectCycle(head)
总结
- 双指针或者快慢指针，虚拟头节点和while循环终止条件，需要手动模拟确认
- 先考虑一般情况，在考虑边界