# 清风的技术小屋

0%

## 问题描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Example 2:

Example 3:

Follow-up:

Can you solve it without using extra space?

Related Topics: Linked List, Two Pointers

## 解决方案

### 解决方案2

• 阶段1 : 首先使用快指针 fast 和慢指针 slow 遍历链表，如果链表有环，两指针最终会相遇到某个节点
• 阶段2 : 初始化额外的两个指针，ptr1 指向链表的头节点，ptr2 指向相遇节点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点

## 问题描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example 1:

Constraints:

• Methods pop, top and getMin operations will always be called on non-empty stacks.

Related Topics: Stack, Design

## 解决方案

• push : push的数据为x，如果x小于min_stack栈顶的值，说明x比现用元素值都要小，则将x压入min_stack，否则将min_stack栈顶的值压入min_stack

## 1. 问题描述

Example:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Related Topics: Linked List

## 2. 解决方案

### 2.1 非递归

1. 首先，我们将黑色节点的下一个节点（即节点6）移动到链表的头部：

2. 然后，我们将黑色节点的下一个节点（即节点15）移动到链表的头部：

3. 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点15

## 问题描述

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Example 2:

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on ...

Related Topics: Linked List

## 问题描述

Remove all elements from a linked list of integers that have value val.

Example:

Related Topics: Linked List

## 问题描述

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Example 2:

Related Topics: Math, Binary Search

## 问题描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Note:

Given n will always be valid.

Could you do this in one pass?

Related Topics: Linked List, Two Pointers

## 问题描述

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Example 2:

Example 3:

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Related Topics: Linked List

## 问题描述

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Example 2:

Example 3:

Can you solve it using O(1) (i.e. constant) memory?

Related Topics: Linked List, Two Pointers

## 问题描述

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Example 2:

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
• The given board contain only digits 1-9 and the character '.'.
• The given board size is always 9x9.

Related Topics: Hash Table

## 解决方案

### 方案1

1. 每行数字有重复数字
2. 每列不能有重复数字
3. 每个 3x3 块中不能有重复数字