# Linked List Cycle I & II

#### Linked List Cycle I 问有没有环

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

Challenge

Can you solve it without using extra space?

Example

Given -21->10->4->5, tail connects to node index 1, return true

```public boolean hasCycle(ListNode head) {
return false;
}
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}```

#### Linked List Cycle II 问环的入口

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

Example

Given -21->10->4->5, tail connects to node index 1，返回10

Challenge

Can you solve it without using extra space?

```public ListNode detectCycle(ListNode head) {
return null;
}
while (fast != null && fast.next != null && slow != fast) {
slow = slow.next;
fast = fast.next.next;
}
if (fast == null || fast.next == null) {
return null;
}
while (runner != slow.next) {
runner = runner.next;
slow = slow.next;
}
return runner;
}```

# Reorder List

Reorder List

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

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

Example

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

Solution: O(n) time and O(1) extra space

Steps:

1. find middle of linked list

2. reverse from mid.next to end as right list

3. Merge left list(from head to mid) and right list(end to mid.next)

```public void reorderList(ListNode head) {
return;
}
ListNode right = mid.next;
right = reverse(right);
mid.next = null;
int count = 0;
while (left != null && right != null) {
if (count % 2 == 0) {
runner.next = left;
left = left.next;
} else {
runner.next = right;
right = right.next;
}
count++;
runner = runner.next;
}
if (left != null) {
runner.next = left;
} else {
runner.next = right;
}
}

ListNode prev = null;
while (runner != null) {
ListNode tmp = runner.next;
runner.next = prev;
prev = runner;
runner = tmp;
}
return prev;
}

}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}```

# Copy List with Random Pointer

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

Challenge

Could you solve it with O(1) space?

## Solution1: O(n) space, using HashMap put save (node, new node) pairs

```public RandomListNode copyRandomList(RandomListNode head) {
//O(n) space version, using hashMap
return null;
}
Map<RandomListNode, RandomListNode> map = new HashMap<>();
//deep copy nodes and next pointers
while (runner.next != null) {
copyRunner.next = new RandomListNode(runner.next.label);
runner = runner.next;
copyRunner = copyRunner.next;
map.put(runner, copyRunner);
}
//deep copy random pointers
for (RandomListNode node : map.keySet()) {
map.get(node).random = map.get(node.random);
}
}```

Solution2: O(1) space

# Convert Sorted List to Binary Search Tree

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.

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

```public TreeNode sortedListToBST(ListNode head) {
return null;
}
TreeNode root = new TreeNode(mid.val);
ListNode midPost = mid.next;
}
root.right = sortedListToBST(midPost);

return root;

}

}
ListNode pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
//Remember to set pre.next = null
if (pre != null) {
pre.next = null;
}
return slow;
}```

# Remove Nth Node From End of List

#### Remove Nth Node From End of List

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

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note

The minimum number of nodes in list is n.

Challenge

O(n) time

Solution: One Pass using Fast Slow Pointers

O(n) time, O(1) space

```ListNode removeNthFromEnd(ListNode head, int n) {
return null;
}
ListNode fast = slow;
for (int i = 0; i < n; i++) {
if (fast.next == null) {
}
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
}```

# Sort List

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Solution: O(nlogn) time. logn layer, each layer takes O(n) time to merge and O(n) time to find middle

1.找中点(findMiddle)

2.两边各自sort

3.Merge

```public ListNode findMiddle(ListNode head) {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

public ListNode merge(ListNode node1, ListNode node2) {
while (node1 != null && node2 != null) {
if (node1.val < node2.val) {
runner.next = node1;
node1 = node1.next;
} else {
runner.next = node2;
node2 = node2.next;
}
runner = runner.next;
}
if (node1 != null) {
runner.next = node1;
} else {
runner.next = node2;
}
}

}
ListNode midPost = mid.next;
mid.next = null;
ListNode right = sortList(midPost);

return merge(left, right);
}```

# Reverse Linked List I & II

Example

Challenge

Reverse it in-place and in one-pass

Solution: In-place and one-pass

```public ListNode reverse(ListNode head) {
}
while (runner != null) {
ListNode next = runner.next;
runner = next;
}
}```

Reverse a linked list from position m to n.

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.

Challenge

Reverse it in-place and in one-pass

```public ListNode reverseBetween(ListNode head, int m , int n) {
}
for (int i = 1; i < m; i++) {
runner = runner.next;
}
ListNode preNode = runner;
ListNode mNode = runner.next;
ListNode nNode = mNode;
ListNode postnNode = nNode.next;
ListNode dummy = new ListNode(0);
for (int i = m; i < n; i++) {
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;
preNode.next = nNode;

}```

# Remove Duplicates from Sorted List I && II

## Remove Duplicates from Sorted List I

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

Example

Given `1->1->2`, return `1->2`.
Given `1->1->2->3->3`, return `1->2->3`.

```public static ListNode deleteDuplicates(ListNode head) {
}
while (runner.next != null) {
if (runner.next.val == runner.val) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
}```

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

Example

Given `1->2->3->3->4->4->5`, return `1->2->5`.
Given `1->1->1->2->3`, return `2->3`.

```    public static ListNode deleteDuplicates(ListNode head) {
}
while(runner.next!=null){
if(runner.next.val==preValue ||
(runner.next.next!=null && runner.next.next.val == runner.next.val)){
preValue = runner.next.val;//keep track of the previous value
runner.next = runner.next.next;//delete runner.next
}else{
preValue = runner.next.val;
runner = runner.next;//keep moving forward
}
}
}```

# Partition List

Lintcode Online Judge

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->null` and x = 3,
return `1->2->2->4->3->5->null`.

```    public ListNode partition(ListNode head, int x) {
ListNode leftDummy = new ListNode(0);
ListNode left = leftDummy;
ListNode rightDummy = new ListNode(0);
ListNode right = rightDummy;
left = left.next;
}else{
right = right.next;
}
}
right.next = null; //important
left.next = rightDummy.next;

return leftDummy.next;
}```

# K Sum

Lintcode Online Judge

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given `[1,2,3,4]`, k = `2`, target = `5`.

There are `2` solutions: `[1,4]` and `[2,3]`.

Return `2`.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x] = 1

O(n*k*t) time O(n*k*t) space

```public int kSum(int A[], int k, int target) {
if (A == null) {
return 0;
}
//kSum[i][j][t]:find j integers from first i integers in the array
//how many solutions there are to sum up to t
int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
for (int i = 0; i <= A.length; i++) {
kSum[i] = 1; //select nothing which is also a solution
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k; j++) {
for (int t = 1; t <= target; t++) {
kSum[i][j][t] = kSum[i - 1][j][t];
if (t >= A[i - 1]) {
kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
}
}
}
}
return kSum[A.length][k][target];
}```