Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
思路：
1.
2.
3.

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路：

1.

2.

3.

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

思路：

1.

2.

3.

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

思路：

1.

2.

3.

Remove Nth Node From End of List

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.
思路：
1.
2.
3.

Rotate List

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

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

思路：

1. 题目中k是非负，所以k可以等于0，k也可以大于链表长。
2. 空链表，单节点以及k为0时，直接返回原链表。
3. 链表长是必须得到的参数。
4. k存在大于链表长度的情况。此时应该用k除以链表长取模，得到真实的反转值。
5. 如果k是链表长度的倍数。直接返回原链表。
6. 双指针，其中从头开始一个先走k%size步，之后双指针同时走，直到先走的指针的next为空。
7. 反转。

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

思路：

1. 与 Remove Duplicates from Sorted List 不同， 这里是要去除所有重复过得节点。

2. 这题很难

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

思路：

1. 分配一个内存空间存之前节点的值。

2. 三个指针，从头到尾撸一遍。如果有重复就删除节点。

3. 记得考虑输入节点为空和单节点的情况。

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

思路：

1. 设置左链和右链，撸一遍。

2. 最后检查左链是否为空。为空则返回右链。

3. 左链不为空，合并左右两链。

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

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

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Reverse Linked List

Reverse a singly linked list.
思路：
1. 首先考虑链表为空和链表只有一个节点的情况。此时无需反转，直接返回原链表。
2. 三个指针
   a) 第一个指针p1指向头指针，
   b) 第二个指针p2指向头指针的next
   c) 第三个指针p3作为缓存，保存第二个指针的next。
3. 注意第一次分配完三个指针后，就可以改变头指针的next为空，以免之后忘记。
4. 开始反转，先保存p2.next到p3，再将p2.next设为p1，最后将p1和p2指针挪到下一步。
5. 重复步骤4，直到p2为空，此时p1即为结果。

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
思路：
1. 第一眼看到以为要先reverse，其实不需要。
2. 考虑两个链表只要有一个为空，就可以直接返回另一个。
3. 双指针分别指向两个链表，一步步做相加，直到其中有一个为空指针。考虑进位。
4. 此时分两种情况讨论
   a) 双指针同时为空，只需考虑进位大于0的情况，加入一个新的节点。
   b) 其中有一个指针为空，则另一个指针进入新的循环，直到另一个指针也为空时结束。
      结束前也需考虑如果进位大于0，则在末尾加入一个新的节点。

Linked List Cycle II

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

Note: Do not modify the linked list.

思路：
1. 首先借用 Linked List Cycle 的结果判断链表是否存在环状结构。
2. 如果不存在返回为空。
3. 使用不同速度的双指针（p1速度为1， p2速度为2）赛跑，直到双指针相遇。
3. 从双指针相遇开始记录环状结构的长度，继续赛跑，直到下一次相遇。
4. 再次相遇时，可以确定慢指针p1从前一次相遇开始到现在走过的步数就是环状结构的长度。
5. 重置双指针，一个先走等同于环状结构长度的步数。一个停留在head。
6. 双指针以相同速度前进，直到它们相遇，此时节点就是环状结构的起始点。

Linked List Cycle

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

Follow up:
Can you solve it without using extra space?
思路：
1. 首先考虑链表为空，链表为单节点以及双节点的特殊情况。
2. 不同速度的双指针（p1速度为1， p2速度为2）赛跑。
3. 赛跑的过程中如果发现快指针p2的next为空就一定没有环。
4. 如果存在环状结构，那么慢指针p1和快指针p2一定会相遇。
5. 如果快慢指针相遇，则一定存在环状结构。

Insert into a Cyclic Sorted List

RT