## Description

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.

## Solution

• 在头部添加一个节点，防止边界溢出。
• 在第一个指针移动到尾部时，第二个指针需要指向移除节点的前一个节点。
• 找到该节点后，将待移除节点的后一节点连接到该节点就相当于完成了节点的移除

# 20. Valid Parentheses

## Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

# 21. Merge Two Sorted Lists

## Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

# 22. Generate Parentheses

## Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

## Example

given n = 3, a solution set is:

# 26. Remove Duplicates from Sorted Array

## Description

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

## Clarification

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

# 28.  Implement strStr()

## Description

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

## Clarification

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

# 29. Divide Two Integers

## Description

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

## Clarification

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31} − 1]$. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

## Solution

• 获取最终结果的符号
• 将除数和被除数转换为长整型计算。
• 分别判断被除数为0和除数为1的情况下的返回值。
• 递归实现其他正常情况下的结果。