Dutch National Flag
static void dutchFlagPartition(List<Integer> A, int pivotIndex) {
int pivot = A.get(pivotIndex);
/**
* Keep the following invariants during partitioning: bottom group:
* A.subList(0, smaller - 1). middle group: A.subList(smaller, curr - 1).
* unclassified group: A.subList(curr, larger). top group: A.subList(larger
* + 1, A.size() - 1).
*/
int smaller = 0, curr = 0, larger = A.size() - 1;
// When there is any unclassified element.
while (curr <= larger) {
// A.get(curr) is the incoming unclassified element.
if (A.get(curr) < pivot) {
swap(A, smaller++, curr++);
} else if (A.get(curr) == pivot) {
++curr;
} else { // A.get(curr) > pivot.
swap(A, curr, larger--);
}
}
}
0 mod n-sum subset
static List<Integer> find0SumSubset(List<Integer> A) {
List<Integer> prefixSum = new ArrayList<Integer>(A);
for (int i = 0; i < prefixSum.size(); ++i) {
prefixSum.set(i, prefixSum.get(i) + (i > 0 ? prefixSum.get(i - 1) : 0));
prefixSum.set(i, prefixSum.get(i) % A.size());
}
List<Integer> table = new ArrayList<Integer>(A.size());
fill(table, A.size(), -1);
for (int i = 0; i < A.size(); ++i) {
if (prefixSum.get(i) == 0) {
List<Integer> ans = new ArrayList<Integer>(i + 1);
iota(ans, i + 1, 0);
return ans;
} else if (table.get(prefixSum.get(i)) != -1) {
List<Integer> ans = new ArrayList<Integer>(i
- table.get(prefixSum.get(i)));
iota(ans, i - table.get(prefixSum.get(i)),
table.get(prefixSum.get(i)) + 1);
return ans;
}
table.set(prefixSum.get(i), i);
}
return Collections.emptyList(); // it should not happen
}
public static void iota(List<Integer> list, int numOfElements, int value) {
for (int i = 1; i <= numOfElements; ++i) {
list.add(value++);
}
}
Print Matrix in Spiral Order
static void printMatrixClockwise(int[][] A, int offset) {
if (offset == A.length - offset - 1) { // for matrix with odd size.
System.out.print(A[offset][offset]);
}
for (int j = offset; j < A.length - offset - 1; ++j) {
System.out.print(A[offset][j] + " ");
}
for (int i = offset; i < A.length - offset - 1; ++i) {
System.out.print(A[i][A.length - offset - 1] + " ");
}
for (int j = A.length - offset - 1; j > offset; --j) {
System.out.print(A[A.length - offset - 1][j] + " ");
}
for (int i = A.length - offset - 1; i > offset; --i) {
System.out.print(A[i][offset] + " ");
}
}
static void printMatrixInSpiralOrder(int[][] A) {
for (int offset = 0; offset < ceil(0.5 * A.length); ++offset) {
printMatrixClockwise(A, offset);
}
}
reverses a singly linked list:
public static <T> Node<T> reverseLinkedList(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> newHead = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static <T> Node<T> reverseLinkedList(Node<T> head) {
Node<T> prev = null, curr = head;
while (curr != null) {
Node<T> temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Write a function that returns null if there does not exist a cycle, and the reference to the start of the cycle if a cycle is present.
Copying Posting List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}
// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}
// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}
// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}
static void rotateMatrix(int[][] A) {
for (int i = 0; i < (A.length >> 1); ++i) {
for (int j = i; j < A.length - i - 1; ++j) {
int temp = A[i][j];
A[i][j] = A[A.length - 1 - j][i];
A[A.length - 1 - j][i] = A[A.length - 1 - i][A.length - 1 - j];
A[A.length - 1 - i][A.length - 1 - j] = A[j][A.length - 1 - i];
A[j][A.length - 1 - i] = temp;
}
}
}
CheckingCycle
class CheckingCycle {
// @include
public static <T> Node<T> hasCycle(Node<T> head) {
Node<T> fast = head;
Node<T> slow = head;
while (slow != null && slow.next != null && fast != null
&& fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // there is a cycle.
// Calculates the cycle length.
int cycleLen = 0;
do {
++cycleLen;
fast = fast.next;
} while (slow != fast);
// Tries to find the start of the cycle.
slow = head;
fast = head;
// Fast pointer advances cycleLen first.
while (cycleLen-- > 0) {
fast = fast.next;
}
// Both pointers advance at the same time.
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // the start of cycle.
}
}
return null; // no cycle.
}
MedianSorted CircularLinkedList
public static double findMedianSortedCircularLinkedList(Node<Integer> rNode) {
if (rNode == null) {
// no node in this linked list.
throw new IllegalArgumentException("empty list");
}
// Checks all nodes are identical or not and identify the start of list.
Node<Integer> curr = rNode;
Node<Integer> start = rNode;
int count = 0;
do {
++count;
curr = curr.next;
// start will point to the largest element in the list.
if (start.data.compareTo(curr.data) <= 0) {
start = curr;
}
} while (curr != rNode);
// start's next is the begin of the list.
start = start.next;
// Traverses to the middle of the list and return the median.
for (int i = 0; i < ((count - 1) >> 1); ++i) {
start = start.next;
}
return (count & 1) != 0 ? start.data : 0.5 * (start.data + start.next.data);
}
OverlappingLists
public static <T> Node<T> overlappingLists(Node<T> L1, Node<T> L2) {
// Store the start of cycle if any.
Node<T> s1 = CheckingCycle.hasCycle(L1), s2 = CheckingCycle.hasCycle(L2);
if (s1 == null && s2 == null) {
return OverlappingListsNoCycle.overlappingNoCycleLists(L1, L2);
} else if (s1 != null && s2 != null) { // both lists have cycles.
Node<T> temp = s2;
do {
temp = temp.next;
} while (temp != s1 && temp != s2);
return (temp == s1) ? s1 : null;
}
return null; // one list has cycle, and one list has no cycle.
}
Reverse LinkedList
public static <T> Node<T> reverseLinkedList(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> newHead = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static <T> Node<T> reverseLinkedList(Node<T> head) {
Node<T> prev = null, curr = head;
while (curr != null) {
Node<T> temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Palindrome LinkedList
public static <T> boolean isLinkedListAPalindrome(Node<T> L) {
// Find the middle point of L if L is odd length,
// and right-middle point if L is even length.
Node<T> slow = L, fast = L;
while (fast != null) {
fast = fast.next;
if (fast != null) {
fast = fast.next;
slow = slow.next;
}
}
// Compare the first half and reversed second half lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
while (reverse != null && L != null) {
if (reverse.data != L.data) {
return false;
}
reverse = reverse.next;
L = L.next;
}
return true;
}
ZippingList
public static <T> Node<T> zippingLinkedList(Node<T> L) {
Node<T> slow = L, fast = L, preSlow = null;
// Find the middle point of L.
while (fast != null) {
fast = fast.next;
if (fast != null) {
preSlow = slow;
fast = fast.next;
slow = slow.next;
}
}
if (preSlow == null) {
return L; // only contains one node in the list.
}
preSlow.next = null; // splits the list into two lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
Node<T> curr = L;
// Zipping the list.
while (curr != null && reverse != null) {
Node<T> temp = curr.next;
curr.next = reverse;
curr = temp;
// Connect curr->next to reverse, and advance curr.
// connectANextToBAdvanceA(ref_curr, reverse);
if (curr != null) {
// Connect reverse->next to curr, and advance reverse.
Node<T> temp2 = reverse.next;
reverse.next = curr;
reverse = temp2;
// connectANextToBAdvanceA(ref_reverse, curr);
}
}
return L;
}
Copying Postings List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}
// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}
// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}
// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}
static void dutchFlagPartition(List<Integer> A, int pivotIndex) {
int pivot = A.get(pivotIndex);
/**
* Keep the following invariants during partitioning: bottom group:
* A.subList(0, smaller - 1). middle group: A.subList(smaller, curr - 1).
* unclassified group: A.subList(curr, larger). top group: A.subList(larger
* + 1, A.size() - 1).
*/
int smaller = 0, curr = 0, larger = A.size() - 1;
// When there is any unclassified element.
while (curr <= larger) {
// A.get(curr) is the incoming unclassified element.
if (A.get(curr) < pivot) {
swap(A, smaller++, curr++);
} else if (A.get(curr) == pivot) {
++curr;
} else { // A.get(curr) > pivot.
swap(A, curr, larger--);
}
}
}
0 mod n-sum subset
static List<Integer> find0SumSubset(List<Integer> A) {
List<Integer> prefixSum = new ArrayList<Integer>(A);
for (int i = 0; i < prefixSum.size(); ++i) {
prefixSum.set(i, prefixSum.get(i) + (i > 0 ? prefixSum.get(i - 1) : 0));
prefixSum.set(i, prefixSum.get(i) % A.size());
}
List<Integer> table = new ArrayList<Integer>(A.size());
fill(table, A.size(), -1);
for (int i = 0; i < A.size(); ++i) {
if (prefixSum.get(i) == 0) {
List<Integer> ans = new ArrayList<Integer>(i + 1);
iota(ans, i + 1, 0);
return ans;
} else if (table.get(prefixSum.get(i)) != -1) {
List<Integer> ans = new ArrayList<Integer>(i
- table.get(prefixSum.get(i)));
iota(ans, i - table.get(prefixSum.get(i)),
table.get(prefixSum.get(i)) + 1);
return ans;
}
table.set(prefixSum.get(i), i);
}
return Collections.emptyList(); // it should not happen
}
public static void iota(List<Integer> list, int numOfElements, int value) {
for (int i = 1; i <= numOfElements; ++i) {
list.add(value++);
}
}
Print Matrix in Spiral Order
static void printMatrixClockwise(int[][] A, int offset) {
if (offset == A.length - offset - 1) { // for matrix with odd size.
System.out.print(A[offset][offset]);
}
for (int j = offset; j < A.length - offset - 1; ++j) {
System.out.print(A[offset][j] + " ");
}
for (int i = offset; i < A.length - offset - 1; ++i) {
System.out.print(A[i][A.length - offset - 1] + " ");
}
for (int j = A.length - offset - 1; j > offset; --j) {
System.out.print(A[A.length - offset - 1][j] + " ");
}
for (int i = A.length - offset - 1; i > offset; --i) {
System.out.print(A[i][offset] + " ");
}
}
static void printMatrixInSpiralOrder(int[][] A) {
for (int offset = 0; offset < ceil(0.5 * A.length); ++offset) {
printMatrixClockwise(A, offset);
}
}
reverses a singly linked list:
public static <T> Node<T> reverseLinkedList(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> newHead = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static <T> Node<T> reverseLinkedList(Node<T> head) {
Node<T> prev = null, curr = head;
while (curr != null) {
Node<T> temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Write a function that returns null if there does not exist a cycle, and the reference to the start of the cycle if a cycle is present.
Copying Posting List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}
// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}
// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}
// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}
static void rotateMatrix(int[][] A) {
for (int i = 0; i < (A.length >> 1); ++i) {
for (int j = i; j < A.length - i - 1; ++j) {
int temp = A[i][j];
A[i][j] = A[A.length - 1 - j][i];
A[A.length - 1 - j][i] = A[A.length - 1 - i][A.length - 1 - j];
A[A.length - 1 - i][A.length - 1 - j] = A[j][A.length - 1 - i];
A[j][A.length - 1 - i] = temp;
}
}
}
CheckingCycle
class CheckingCycle {
// @include
public static <T> Node<T> hasCycle(Node<T> head) {
Node<T> fast = head;
Node<T> slow = head;
while (slow != null && slow.next != null && fast != null
&& fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // there is a cycle.
// Calculates the cycle length.
int cycleLen = 0;
do {
++cycleLen;
fast = fast.next;
} while (slow != fast);
// Tries to find the start of the cycle.
slow = head;
fast = head;
// Fast pointer advances cycleLen first.
while (cycleLen-- > 0) {
fast = fast.next;
}
// Both pointers advance at the same time.
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // the start of cycle.
}
}
return null; // no cycle.
}
MedianSorted CircularLinkedList
public static double findMedianSortedCircularLinkedList(Node<Integer> rNode) {
if (rNode == null) {
// no node in this linked list.
throw new IllegalArgumentException("empty list");
}
// Checks all nodes are identical or not and identify the start of list.
Node<Integer> curr = rNode;
Node<Integer> start = rNode;
int count = 0;
do {
++count;
curr = curr.next;
// start will point to the largest element in the list.
if (start.data.compareTo(curr.data) <= 0) {
start = curr;
}
} while (curr != rNode);
// start's next is the begin of the list.
start = start.next;
// Traverses to the middle of the list and return the median.
for (int i = 0; i < ((count - 1) >> 1); ++i) {
start = start.next;
}
return (count & 1) != 0 ? start.data : 0.5 * (start.data + start.next.data);
}
OverlappingLists
public static <T> Node<T> overlappingLists(Node<T> L1, Node<T> L2) {
// Store the start of cycle if any.
Node<T> s1 = CheckingCycle.hasCycle(L1), s2 = CheckingCycle.hasCycle(L2);
if (s1 == null && s2 == null) {
return OverlappingListsNoCycle.overlappingNoCycleLists(L1, L2);
} else if (s1 != null && s2 != null) { // both lists have cycles.
Node<T> temp = s2;
do {
temp = temp.next;
} while (temp != s1 && temp != s2);
return (temp == s1) ? s1 : null;
}
return null; // one list has cycle, and one list has no cycle.
}
Reverse LinkedList
public static <T> Node<T> reverseLinkedList(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> newHead = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static <T> Node<T> reverseLinkedList(Node<T> head) {
Node<T> prev = null, curr = head;
while (curr != null) {
Node<T> temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
Palindrome LinkedList
public static <T> boolean isLinkedListAPalindrome(Node<T> L) {
// Find the middle point of L if L is odd length,
// and right-middle point if L is even length.
Node<T> slow = L, fast = L;
while (fast != null) {
fast = fast.next;
if (fast != null) {
fast = fast.next;
slow = slow.next;
}
}
// Compare the first half and reversed second half lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
while (reverse != null && L != null) {
if (reverse.data != L.data) {
return false;
}
reverse = reverse.next;
L = L.next;
}
return true;
}
ZippingList
public static <T> Node<T> zippingLinkedList(Node<T> L) {
Node<T> slow = L, fast = L, preSlow = null;
// Find the middle point of L.
while (fast != null) {
fast = fast.next;
if (fast != null) {
preSlow = slow;
fast = fast.next;
slow = slow.next;
}
}
if (preSlow == null) {
return L; // only contains one node in the list.
}
preSlow.next = null; // splits the list into two lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
Node<T> curr = L;
// Zipping the list.
while (curr != null && reverse != null) {
Node<T> temp = curr.next;
curr.next = reverse;
curr = temp;
// Connect curr->next to reverse, and advance curr.
// connectANextToBAdvanceA(ref_curr, reverse);
if (curr != null) {
// Connect reverse->next to curr, and advance reverse.
Node<T> temp2 = reverse.next;
reverse.next = curr;
reverse = temp2;
// connectANextToBAdvanceA(ref_reverse, curr);
}
}
return L;
}
Copying Postings List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}
// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}
// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}
// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}
