com.sl.algorithms.core.utils

Class LinkedListOps

java.lang.Object

com.sl.algorithms.core.utils.LinkedListOps

public class LinkedListOps
extends java.lang.Object

Method Summary

Modifier and Type	Method and Description
static ListNode<java.lang.Integer>	incrementByOne(ListNode<java.lang.Integer> head)
static <T extends java.lang.Comparable> ListNode<T>	insertData(ListNode<T> head, T newData, OpPosition position)
static <T extends java.lang.Comparable> boolean	isPalindrome(ListNode<T> head) Palindrome Linked List
static <T extends java.lang.Comparable> ListNode<T>	removeData(ListNode<T> head, T data)
static <T extends java.lang.Comparable> ListNode<T>	removeDataByPosition(ListNode<T> head, OpPosition position)
static <T extends java.lang.Comparable> ListNode<T>	removeDuplicates(ListNode<T> head)
static <T extends java.lang.Comparable> ListNode<T>	reorderList(ListNode<T> head) Reorder List Approach: Find the mid-point; break the list into 2 parts around the mid-point; establish new links.
static <T extends java.lang.Comparable> ListNode<T>	reverse(ListNode<T> head) O(n) time and O(1) space method to reverse a list.
static <T extends java.lang.Comparable> ListNode<T>	reverseListInGroups(ListNode<T> head, int k) O(n) time and O(n/kMax) recursion-space method to reverse list in groups of kMax.
static <T extends java.lang.Comparable> ListNode<T>	swapInPairs(ListNode<T> head) O(n) time and O(n/2) recursion-space method to swap/reverse in pairs.

Methods inherited from class java.lang.Object

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

Method Detail

insertData

public static <T extends java.lang.Comparable> ListNode<T> insertData(ListNode<T> head,
                                                                      T newData,
                                                                      OpPosition position)

removeDataByPosition

public static <T extends java.lang.Comparable> ListNode<T> removeDataByPosition(ListNode<T> head,
                                                                                OpPosition position)

removeData

public static <T extends java.lang.Comparable> ListNode<T> removeData(ListNode<T> head,
                                                                      T data)

removeDuplicates

public static <T extends java.lang.Comparable> ListNode<T> removeDuplicates(ListNode<T> head)

reverse

public static <T extends java.lang.Comparable> ListNode<T> reverse(ListNode<T> head)

O(n) time and O(1) space method to reverse a list.

Type Parameters:

T - Comparable

Parameters:

head - input list

Returns:

reversed list

reverseListInGroups

public static <T extends java.lang.Comparable> ListNode<T> reverseListInGroups(ListNode<T> head,
                                                                               int k)

O(n) time and O(n/kMax) recursion-space method to reverse list in groups of kMax.

Type Parameters:

T - Comparable

Parameters:

head - input list

k - batch-size

Returns:

reversed list

swapInPairs

public static <T extends java.lang.Comparable> ListNode<T> swapInPairs(ListNode<T> head)

O(n) time and O(n/2) recursion-space method to swap/reverse in pairs.

Type Parameters:

T - Comparable

Parameters:

head - input list

Returns:

transformed list

incrementByOne

public static ListNode<java.lang.Integer> incrementByOne(ListNode<java.lang.Integer> head)

reorderList

public static <T extends java.lang.Comparable> ListNode<T> reorderList(ListNode<T> head)

Reorder List

Approach: Find the mid-point; break the list into 2 parts around the mid-point; establish new links.

Type Parameters:

T - Comparable

Parameters:

head - input list

Returns:

re-ordered list

isPalindrome

public static <T extends java.lang.Comparable> boolean isPalindrome(ListNode<T> head)

Palindrome Linked List

Type Parameters:

T - Comparable

Parameters:

head - input list

Returns:

true, when the list follows a palindrome pattern