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

Ashes To Glory: Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)

You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.

Rotate by +90 (clockwise once):

Input: n by n matrix M, where n >= 2

Algorithm:

Step 1: Transpose M

Step 2: Reverse each row

Dry run:

Step 1: Transpose

M                   M'

1 2 3              1 4 7

4 5 6      --     2 5 8

7 8 9              3 6 9

Step 2: Reverse each row

M'                  M''

1 4 7              7 4 1
2 5 8      --     8 5 2
3 6 9              9 6 3

Pseudocode: is here which is self explanatory and easily convertible to source code in a language of your choice.

Transpose

    for i in [0, n)

        for j in [0, n)

            if ( i < j )

                swap( M[i][j], M[j][i] )

Reverse a row (rowidx)

    start = 0

    end = cols - 1

    while ( start < end ) {

        swap( M[rowidx][start], M[rowidx][end] )

        ++start

        --end

    }

Rotate

    Transpose

    for i in [0, rows)

        Reverse( i )

That was fair enough until only asked to rotate by +90 degree. If problem is further extended to be solved for any given angle, of course the rotation should make sense, for example, 47 degree is not a choice ;-). So, here are some elegant techniques (I'll be brief now for other angles, because for +90 degree I have elaborated the solution):

Rotation by -90 degree (anticlockwise once):

Step 1: Transpose

Step 2: Reverse each column

Rotation by +180 degree (clockwise twice): Two methods follows

First:

Rotate input matrix +90 degree twice, if routine for which is available to you

Second: (You'll be amazed!)

Step 1: Reverse each row

Step 2: Reverse each column

Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows

First:

Rotate input matrix -90 degree twice, if routine for which is available to you

Second: (You'll be amazed again!)

Step 1: Reverse each column

Step 2: Reverse each row

Third: (Aha!)

Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.

Turn an image by 90 degree

From http://www.geeksforgeeks.org/turn-an-image-by-90-degree/

for(r = 0; r < m; r++)
{
   for(c = 0; c < n; c++)
   {
      // Hint: Map each source element indices into
      // indices of destination matrix element.
       dest_buffer [ c ] [ m - r - 1 ] = source_buffer [ r ] [ c ];
   }
}

Code From http://www.emanueleferonato.com/2012/11/07/how-to-rotate-a-two-dimensional-array-by-90-degrees-clockwise-or-counter-clockwise-like-knightfall-game/

        private function rotateCounterClockwise(a:Array):void {

            var n:int=a.length;

            for (var i:int=0; i<n/2; i++) {

                for (var j:int=i; j<n-i-1; j++) {

                    var tmp:String=a[i][j];

                    a[i][j]=a[j][n-i-1];

                    a[j][n-i-1]=a[n-i-1][n-j-1];

                    a[n-i-1][n-j-1]=a[n-j-1][i];

                    a[n-j-1][i]=tmp;

                }

            }

        }

        private function rotateClockwise(a:Array):void {

            var n:int=a.length;

            for (var i:int=0; i<n/2; i++) {

                for (var j:int=i; j<n-i-1; j++) {

                    var tmp:String=a[i][j];

                    a[i][j]=a[n-j-1][i];

                    a[n-j-1][i]=a[n-i-1][n-j-1];

                    a[n-i-1][n-j-1]=a[j][n-i-1];

                    a[j][n-i-1]=tmp;

                }

            }

        }

http://analgorithmaday.blogspot.com/2011/04/rotate-array90.html
Read full article from Ashes To Glory: Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)