# LeetCode 88. Merge Sorted Array

## Description

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.

• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

``````Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
``````

`nums1``nums2`两个有序数组合并到`nums1`一个中，`nums1`已分配足够空间存放元素。

# LeetCode 86. Partition List

## Description

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

``````Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
``````

# LeetCode 80. Remove Duplicates from Sorted Array II

## Description

Remove Duplicates from Sorted Array II

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice 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.

Example 1:

``````Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements
of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.
``````

Example 2:

``````Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements
of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.
``````

# LeetCode 75. Sort Colors

## Description

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers `0`, `1`, and `2` to represent the color `red`, `white`, and `blue` respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

``````Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
``````
• A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

• Could you come up with a one-pass algorithm using only constant space?

# LeetCode 61. Rotate List

## Description

Rotate List

Given a linked list, rotate the list to the right by `k` places, where `k` is non-negative.

Example 1:

``````Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
``````

Example 2:

``````Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
``````

# LeetCode 19. Remove Nth Node From End of List

Remove Nth Node From End of List

## Description

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

``````For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
``````

Note: Given n will always be valid. Try to do this in one pass.

# LeetCode 18. 4Sum

4Sum

## Description

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

``````For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]
``````

# LeetCode 15. 3Sum

3Sum

## Description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

``````For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

Programer

ChengDu·China