【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表

class?Solution:

????def?moveZeroes(self,?nums:?List[int])?->?None:

????????"""

????????Do not return anything, modify nums in-place instead.

????????"""

????????left =?0

????????n =?len(nums)

????????for?i in?range(n):

????????????if?nums[i]?!=?0:

????????????????nums[left],nums[i]?=?nums[i],nums[left]

????????????????left +=?1

????????return?nums

class?Solution:

????def?moveZeroes(self,?nums:?List[int])?->?None:

????????"""

????????Do not return anything, modify nums in-place instead.

????????"""

????????j =?0

????????for?i in?range(len(nums)):

????????????if?nums[i]?!=?0:

????????????????nums[j]?=?nums[i]

????????????????if?i !=?j:

????????????????????nums[i]?=?0

????????????????j +=?1

????????return?nums

#?迭代

class?Solution:

????def?swapPairs(self,?head:?ListNode)?->?ListNode:

????????# 通过迭代实现

????????dummy =?ListNode(-1)

????????dummy.next?=?head

????????prev_node =?dummy

????????while?head and?head.next:

????????????first_node =?head

????????????second_node =?head.next

????????????# 交换节点

????????????prev_node.next?=?second_node

????????????first_node.next?=?second_node.next

????????????second_node.next?=?first_node

????????????# 初始化头节点与prev_node

????????????prev_node =?first_node

????????????head =?first_node.next

????????return?dummy.next

#?递归

class?Solution:

????def?swapPairs(self,?head:?ListNode)?->?ListNode:

????????# 递归实现

????????if?not?head or?not?head.next:

????????????return?head

????????first_node =?head

????????second_node =?head.next

????????# 第二个节点的next节点作为头部传入递归函数，返回的是

????????# 指向第二个节点的指针

????????first_node.next?=?self.swapPairs(second_node.next)

????????second_node.next?=?first_node

????????return?second_node

# 迭代

class?Solution:

????def?reverseList(self,?head:?ListNode)?->?ListNode:

????????if?head is?None:

????????????return?head

????????pre =?None

????????cur =?head

????????while?cur:

????????????nxt =?cur.next

????????????cur.next?=?pre

????????????pre =?cur

????????????cur =?nxt

????????return?pre

# 递归

class?Solution:

????def?reverseList(self,?head:?ListNode)?->?ListNode:

????????if?not?head or?not?head.next:

????????????return?head

????????last =?self.reverseList(head.next)

????????head.next.next?=?head

????????head.next?=?None

????????return?last