# LeetCode Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.


Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.


Note:

• The number of nodes in the given list will be between 1 and 100.

class Solution {
public:
while (fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == NULL)break;
}
return slow;
}
};

# LeetCode Reorder List

143. Reorder List

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

class Solution {
public:
{
return; // find mid node
while (slow->next != NULL && fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
// reverse [mid,end]
ListNode *par = new ListNode(0), *tail;
while (slow) {
tail = slow->next;
slow->next = par->next;
par->next = slow;
slow = tail;
}
//merge 2 list
par = par->next;
h->next = par;
par = par->next;
}
else {
h = h->next;
h->next = par;
par = par->next;
}
h = h->next;
}
}
};

# LeetCode Odd Even Linked List

LeetCode Odd Even Linked List 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: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. 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 …

# LeetCode Find the Duplicate Number

287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2


Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

class Solution {
public:
int findDuplicate(vector<int>& nums)
{
int low = 1, high = nums.size() – 1;
while (low < high) {
int mid = (low + high) / 2, low_cnt = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] <= mid)
++low_cnt;
}
if (low_cnt > mid) {
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
};

class Solution {
public:
int findDuplicate(vector<int>& nums)
{
int slow = 0, fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast)
break;
}
slow = 0;
while (true) {
slow = nums[slow];
fast = nums[fast];
if (slow == fast)
return slow;
}
}
};

l、r、while(l<=r)都是标准的二分搜索框架。最后返回r+1，想象一直low_cnt>m，知道不满足while循环，则最后一个满足的就是r+1。

class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int l = 1, r = n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
int low_cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] <= m)++low_cnt;
}
if (low_cnt > m)r = m - 1;
else l = m + 1;
}
return r + 1;
}
};

# LeetCode Linked List Cycle II

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:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.


Follow-up:
Can you solve it without using extra space?

class Solution {
public:
{
return NULL;
while (faster->next != NULL && faster->next->next != NULL) {
faster = faster->next->next;
slower = slower->next;
if (faster == slower)
break;
}
if (faster->next == NULL || faster->next->next == NULL)
return NULL;
while (slower != faster) {
slower = slower->next;
faster = faster->next;
}
return slower;
}
};

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:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.


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

a+b+mc=s—(1)

a+b+nc=2s—-(2)

(1)和(2)式分别为慢快指针的等式，其中s表示慢指针走过的节点，则快指针走过两倍的s，m和n分别为慢快指针绕圈的圈数，显然n>m。 把(1)代入(2)得到a+b=(n-2m)c。假设真的存在环，则a和c是链表的固有值，是已知量，所以如果能找到m,n,b的一组解，则说明假设成立，真的存在环。 令m=0,n=a,b=ac-a，则这一组解是满足上面的方程(1)和(2)的，也满足n>m。因为环的长度>1，所以b也是大于0的。既然找到一组解，说明假设成立，即存在环。也就是说，我们可以用这种方法判断环是否存在。 完整代码如下：

class Solution {
public:
{
return false;
while (faster->next != NULL && faster->next->next != NULL) {
faster = faster->next->next;
slower = slower->next;
if (faster == slower)
return true;
}
return false;
}
};

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Could you do it in O(n) time and O(1) space?

1. 1->2->3->4->5->4->3->2->1
2. 1->2->3->4->4->3->2->1

class Solution {
public:
{
return true;
while (faster->next != NULL && faster->next->next != NULL) {
faster = faster->next->next;
slower = slower->next;
} //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
ListNode *head2 = slower, *prior = slower->next, *tail;
while (prior != NULL) { // 逆序后半段链表
tail = prior->next;
prior = tail;
}
return false;
}
return true;
}
};

class Solution {
public:
// 快慢指针
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
// 逆序后半段
ListNode *dummy = new ListNode(0);
ListNode *par = slow, *child = slow->next;
while (par != NULL) {
child = par->next;
par->next = dummy->next;
dummy->next = par;
par = child;
}
// 判断是否相等
fast = dummy->next;
while (fast != NULL) {
if (slow->val != fast->val)return false;
slow = slow->next;
fast = fast->next;
}
return true;
}
};

# LeetCode Convert Sorted List to Binary Search Tree

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5

class Solution {
public:
{
return NULL;
int n = 0, cnt = 0;
while (tmp != NULL) {
n++;
tmp = tmp->next;
}
while (cnt < n / 2 – 1) {
tmp = tmp->next;
cnt++;
} // 此时tmp是中间节点的上一个节点
TreeNode* root = new TreeNode(tmp->next->val);
tmp->next = NULL; // 断开
return root;
}
};

class Solution {
public:
{
return NULL;
while (fast->next != NULL && fast->next->next != NULL) {
prior = slow;
slow = slow->next;
fast = fast->next->next;
} // 此时slow为中间节点，prior为中间节点的上一个节点
TreeNode* root = new TreeNode(slow->val);
prior->next = NULL; //断开
return root;
}
};

# LeetCode 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

class Solution {
public:
{
if (head == NULL || head->next == NULL || k == 0)
int n = 1, cut_pos = 0;
while (tail->next != NULL) {
n++;
tail = tail->next;
}
//while (k >= n)k -= n;
k = k % n;
if (k == 0)
while (cut_pos + k + 1 < n) {
new_tail = new_tail->next;
cut_pos++;
}
new_tail->next = NULL;
}
};

class Solution {
public:
int len = 0;
++len;
}
return len;
}
ListNode* rotateRight(ListNode* head, int k) {
if (len == 0 || len == 1)return head;
k = k % len;
int l = len - k;
while (--l) { // 注意是--l，不是l--，停在断开前一个位置
first = first->next;
}
ListNode *second = first->next;
first->next = NULL;
first = second;
while (first->next)first = first->next;
return second;
}
};

# LeetCode Remove Element

Given an array nums and a value val, remove all instances of that value in-place 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.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

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


Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

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

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:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return (nums[0] != val) ? 1 : 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == val) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] != val) {
nums[i] = nums[j];
nums[j] = val;
break;
}
}
}
}
if (nums[0] == val)
return 0;
else {
int i;
for (i = nums.size() – 1; i >= 0; i–)
if (nums[i] != val)
break;
return i + 1;
}
}
};

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size(), i = -1;
for (int j = 0; j < n; ++j) {
if (nums[j] != val)nums[++i] = nums[j];
}
return i + 1;
}
};