Chapter 7: Array and LinkedList Algorithm from Elements of Programming Interviews

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;
}