Chapter 7: LinkedList Algorithm from Elements of Programming Interviews

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