【经典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