com.sl.algorithms.core.list.rotation

Class LinkedListRotation<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.core.list.rotation.LinkedListRotation<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, RotationEngine<T>

public class LinkedListRotation<T extends java.lang.Comparable>
extends java.lang.Object
implements RotationEngine<T>

Requirement: rotate w/in O(n) time and O(1) space.

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
LinkedListRotation()

Method Summary

Modifier and Type	Method and Description
ListNode<T>	rotate(ListNode<T> head, int k, boolean clockwise) Approach: 0.
T[]	rotate(T[] objects, int k, boolean clockwise)
ListNode<T>	rotateListLeft(ListNode<T> head, int k)
ListNode<T>	rotateListRight(ListNode<T> head, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sl.algorithms.core.interfaces.rotate.RotationEngine

isRotation, isRotation

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

LinkedListRotation

public LinkedListRotation()

Method Detail

rotate

public ListNode<T> rotate(ListNode<T> head,
                          int k,
                          boolean clockwise)

Approach:
0. If kMax%size or kMax == 0 then no/full rotation.
1. Track 2 pointers, one for originalTail and second for newTail.
2. Join originalTail with originalHead.
3. newTail : right=(n-kMax) | left=(kMax)
4. newHead = newTail.next, newTail.next = null.
5. Handle scenario when kMax is greater than the size of the list (solution: kMax = kMax%size).

Specified by:

rotate in interface RotationEngine<T extends java.lang.Comparable>

rotateListLeft

public ListNode<T> rotateListLeft(ListNode<T> head,
                                  int k)

rotateListRight

public ListNode<T> rotateListRight(ListNode<T> head,
                                   int k)

rotate

public T[] rotate(T[] objects,
                  int k,
                  boolean clockwise)

Specified by:

rotate in interface RotationEngine<T extends java.lang.Comparable>