import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.HashMap;
import org.apache.commons.io.IOUtils;
//
public class LinkedList3<T>
{
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception
{
LinkedList3<Integer> list = new LinkedList3<Integer>(1, 2, 3, 4, 5);
// System.out.println(list.isEmpty());
// System.out.println(list.size());
System.out.println(list);
// Entry<Integer> entry = list.getEntry(2);
// LinkedList3<Integer> n_list = (LinkedList3<Integer>) list.clone();
// System.out.println(n_list);
// LinkedList3.reverseListByIterator(n_list);
// LinkedList3.reverseListByRecursion(n_list);
// System.out.println(n_list);
// Entry<Integer> entry = LinkedList3.lastIndexOf(list, 6);
// Entry<Integer> entry = LinkedList3.lastIndexOfByArray(list, 2);
// Entry<Integer> entry = LinkedList3.getMiddleEntry(list);
// LinkedList3.reversePrintListByStack(list);
// LinkedList3.reversePrintListByRecursion(list);
// LinkedList3<Integer> list1 = new LinkedList3<Integer>();
// LinkedList3<Integer> list2 = new LinkedList3<Integer>(2, 3, 4, 5);
// System.out.println(list1);
// System.out.println(list2);
// LinkedList3<Integer> list3 = LinkedList3.mergeList(list1, list2);
// System.out.println(list3);
// LinkedList3<Integer> list1 = new LinkedList3<Integer>(1, 2, 3, 4);
// list1.getEntry(3).setNext(list1.getEntry(3));
// System.out.println(LinkedList3.hasLoop(list1));
// Entry<Integer> entry = LinkedList3.getFirstEnterLoopEntry(list1);
// Entry<Integer> entry = LinkedList3.getFirstEnterLoopEntry2(list1);
// LinkedList3<Integer> list1 = new LinkedList3<Integer>(1, 2, 3, 4, 5);
// LinkedList3<Integer> list2 = new LinkedList3<Integer>(11, 22, 33, 44,
// 55);
// list2.getEntry(1).setNext(list1.getEntry(0));
// list2.getEntry(3).setNext(list1.getEntry(2));
// System.out.println(list1);
// System.out.println(list2);
// System.out.println(LinkedList3.isIntersect(list1, list2));
// System.out.println(LinkedList3.isIntersect2(list1, list2));
// System.out.println(LinkedList3.isIntersect3(list1, list2));
//
// Entry<Integer> entry = LinkedList3.getFirstIntersectEntry(list1,
// list2);
// System.out.println(entry == null ? "not found" : entry.element);
// LinkedList3.deleteEntry(list, list.getEntry(0));
// System.out.println(list);
}
//
private Entry<T> head;
public LinkedList3()
{
//
head = null;
}
public LinkedList3(T... elements)
{
this();
Entry<T> tail = head;
for (T element : elements)
{
Entry<T> newEntry = new Entry<T>(element);
//
if (head == null)
{
head = newEntry;
tail = head;
}
else
{
// ，
tail.next = newEntry;
tail = newEntry;
}
}
}
public boolean isEmpty()
{
return head == null;
}
// 1.
public int size()
{
if (isEmpty())
return 0;
Entry<T> curEntry = head;
int c = 0;
while (curEntry != null)
{
c++;
curEntry = curEntry.next;
}
return c;
}
// 2. : reverseList（ ）
public static <T> void reverseListByIterator(LinkedList3<T> list)
{
Entry<T> curEntry = list.head;
Entry<T> nextEntry = null;
Entry<T> nextnextEntry = null;
if (curEntry == null || curEntry.next == null)
return;
while (curEntry.next != null)
{
nextEntry = curEntry.next;
nextnextEntry = nextEntry.next;
nextEntry.next = list.head;
list.head = nextEntry;
curEntry.next = nextnextEntry;
}
}
// 2. : reverseListRec（ ）
public static <T> void reverseListByRecursion(LinkedList3<T> list)
{
if (list.head == null || list.head.next == null)
return;
list.head = reverseList(list.head);
}
private static <T> Entry<T> reverseList(Entry<T> entry)
{
if (entry.next == null)
return entry;
Entry<T> newHead = reverseList(entry.next);
entry.next.next = entry;
entry.next = null;
return newHead;
}
// 3. K （k > 0）
public static <T> Entry<T> lastIndexOf(LinkedList3<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The input number should be greater than zero");
Entry<T> first = list.getEntry(n - 1);
Entry<T> second = list.head;
while (first.next != null)
{
first = first.next;
second = second.next;
}
return second;
}
// 3. K （k > 0）,
@SuppressWarnings("unchecked")
public static <T> Entry<T> lastIndexOfByArray(LinkedList3<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The input number should be greater than zero");
Object[] storage = new Object[n];
int index = 0, c = 0;
Entry<T> curEntry = list.head;
while (curEntry != null)
{
storage[index] = curEntry;
curEntry = curEntry.next;
index = (index + 1) % n;
c++;
}
if (storage[index] == null)
throw new IllegalStateException("less than " + n + " elemements, current is " + c);
return Entry.class.cast(storage[index]);
}
// 4.
public static <T> Entry<T> getMiddleEntry(LinkedList3<T> list)
{
if (list.isEmpty())
return null;
Entry<T> first = list.head;
Entry<T> second = list.head;
while (first.next != null && first.next.next != null)
{
first = first.next.next;
second = second.next;
}
return second;
}
// 5. ,
public static <T> void reversePrintListByStack(LinkedList3<T> list)
{
java.util.LinkedList<Entry<T>> stack = new java.util.LinkedList<Entry<T>>();
Entry<T> curEntry = list.head;
while (curEntry != null)
{
stack.push(curEntry);
curEntry = curEntry.next;
}
String result = "[";
while (!stack.isEmpty())
result += stack.pop().element + ", ";
if (result.length() > 1)
result = result.substring(0, result.length() - 2);
result += "]";
System.out.println(result);
}
// 5. （ ）
public static <T> void reversePrintListByRecursion(LinkedList3<T> list)
{
String result = reversePrintList(list.head);
if (result.length() > 0)
result = result.substring(0, result.length() - 2);
result = "[" + result + "]";
System.out.println(result);
}
private static <T> String reversePrintList(Entry<T> entry)
{
if (entry == null)
return "";
String result = reversePrintList(entry.next);
result += entry.element;
return result + ", ";
}
// 6. list1 list2 ，
@SuppressWarnings("unchecked")
public static <T> LinkedList3<T> mergeList(LinkedList3<T> list1, LinkedList3<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
Entry<T> newHead = null;
Entry<T> curEntry = newHead;
//
if (curEntry1 != null && curEntry2 != null)
{
if (((Comparable) curEntry1.element).compareTo(curEntry2.element) < 0)
{
newHead = new Entry(curEntry1.element, null);
curEntry1 = curEntry1.next;
}
else
{
newHead = new Entry(curEntry2.element, null);
curEntry2 = curEntry2.next;
}
curEntry = newHead;
}
else if (curEntry1 != null)
{
newHead = new Entry(curEntry1.element, null);
curEntry = newHead;
curEntry1 = curEntry1.next;
}
else if (curEntry2 != null)
{
newHead = new Entry(curEntry2.element, null);
curEntry = newHead;
curEntry2 = curEntry2.next;
}
while (curEntry1 != null && curEntry2 != null)
{
if (((Comparable) curEntry1.element).compareTo(curEntry2.element) < 0)
{
curEntry.next = new Entry(curEntry1.element, null);
curEntry = curEntry.next;
curEntry1 = curEntry1.next;
}
else
{
curEntry.next = new Entry(curEntry2.element, null);
curEntry = curEntry.next;
curEntry2 = curEntry2.next;
}
}
while (curEntry1 != null)
{
curEntry.next = new Entry(curEntry1.element, null);
curEntry = curEntry.next;
curEntry1 = curEntry1.next;
}
while (curEntry2 != null)
{
curEntry.next = new Entry(curEntry2.element, null);
curEntry = curEntry.next;
curEntry2 = curEntry2.next;
}
LinkedList3<T> result = new LinkedList3<T>();
result.setHead(newHead);
return result;
}
// 7.
public static <T> boolean hasLoop(LinkedList3<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
if (first == second)
return true;
}
return false;
}
// 8. ，
public static <T> Entry<T> getFirstEnterLoopEntry(LinkedList3<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
if (first == second)
break;
}
if (first == null || first.next == null)
return null;
second = list.head;
while (first != second)
{
first = first.next;
second = second.next;
}
return first;
}
// 8. ， HashMap
public static <T> Entry<T> getFirstEnterLoopEntry2(LinkedList3<T> list)
{
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
Entry<T> curEntry = list.head;
while (curEntry != null)
{
if (storage.get(curEntry) == Boolean.TRUE)
return curEntry;
else
{
storage.put(curEntry, Boolean.TRUE);
curEntry = curEntry.next;
}
}
return null;
}
// 9. HashMap
public static <T> boolean isIntersect(LinkedList3<T> list1, LinkedList3<T> list2)
{
if (list1.isEmpty() || list2.isEmpty())
return false;
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
Entry<T> curEntry1 = list1.head;
while (curEntry1 != null)
{
storage.put(curEntry1, Boolean.TRUE);
curEntry1 = curEntry1.next;
}
Entry<T> curEntry2 = list2.head;
while (curEntry2 != null)
{
if (storage.get(curEntry2) == Boolean.TRUE)
return true;
curEntry2 = curEntry2.next;
}
return false;
}
// 9. next ，
public static <T> boolean isIntersect2(LinkedList3<T> list1, LinkedList3<T> list2)
{
if (list1.isEmpty() || list2.isEmpty())
return false;
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
while (curEntry1.next != null)
curEntry1 = curEntry1.next;
curEntry1.next = list2.head;
boolean exist = false;
while (curEntry2.next != null)
{
if (curEntry2.next == list2.head)
{
exist = true;
break;
}
curEntry2 = curEntry2.next;
}
curEntry1.next = null;
return exist;
}
// 9.
public static <T> boolean isIntersect3(LinkedList3<T> list1, LinkedList3<T> list2)
{
if (list1.isEmpty() || list2.isEmpty())
return false;
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
while (curEntry1.next != null)
curEntry1 = curEntry1.next;
while (curEntry2.next != null)
curEntry2 = curEntry2.next;
if (curEntry1 == curEntry2)
return true;
return false;
}
// 10.
public static <T> Entry<T> getFirstIntersectEntry(LinkedList3<T> list1, LinkedList3<T> list2)
{
int m = list1.size();
int n = list2.size();
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
int c;
if (m > n)
{
c = m - n;
while (c != 0)
{
curEntry1 = curEntry1.next;
c--;
}
}
else
{
c = n - m;
while (c != 0)
{
curEntry2 = curEntry2.next;
c--;
}
}
while (curEntry1 != null)
{
if (curEntry1 == curEntry2)
return curEntry1;
curEntry1 = curEntry1.next;
curEntry2 = curEntry2.next;
}
return null;
}
// 11. pHead pToBeDeleted，O(1) pToBeDeleted: delete
public static <T> void deleteEntry(LinkedList3<T> list, Entry<T> entry)
{
if (entry == null)
return;
if (entry.next != null)
{
entry.element = entry.next.element;
entry.next = entry.next.next;
}
else
{
if (entry == list.head)
list.head = entry.next;
else
{
Entry<T> preEntry = list.head;
while (preEntry != null)
{
if (preEntry.next == entry)
break;
preEntry = preEntry.next;
}
preEntry.next = preEntry.next.next;
}
}
}
public void setHead(Entry<T> head)
{
this.head = head;
}
public Entry<T> createEntry(T element)
{
return new Entry<T>(element);
}
public Entry<T> getEntry(int index)
{
if (index < 0)
throw new IllegalArgumentException("index should be a positive number or zero");
int c = 0;
Entry<T> curEntry = head;
while (curEntry != null && c < index)
{
c++;
curEntry = curEntry.next;
}
if (curEntry == null)
throw new IllegalStateException("less than " + (index + 1) + " elements, current is " + c);
return curEntry;
}
@SuppressWarnings("unchecked")
@Override
public Object clone() throws CloneNotSupportedException
{
try
{
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
try
{
oos.writeObject(head);
oos.flush();
ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
try
{
LinkedList3<T> result = new LinkedList3<T>();
result.setHead(Entry.class.cast(ois.readObject()));
return result;
}
finally
{
IOUtils.closeQuietly(ois);
}
}
finally
{
IOUtils.closeQuietly(oos);
}
}
catch (Exception e)
{
e.printStackTrace();
return super.clone();
}
}
@Override
public String toString()
{
String result = "[";
Entry<T> curEntry = head;
while (curEntry != null)
{
result += curEntry.element;
curEntry = curEntry.next;
if (curEntry != null)
result += ", ";
}
return result + "]";
}
public static class Entry<T> implements Serializable
{
private static final long serialVersionUID = 1L;
T element;
Entry<T> next;
Entry(T element)
{
this(element, null);
}
Entry(T element, Entry<T> next)
{
this.element = element;
this.next = next;
}
public void setElement(T element)
{
this.element = element;
}
public T getElement()
{
return element;
}
public void setNext(Entry<T> next)
{
this.next = next;
}
public Entry<T> getNext()
{
return next;
}
@Override
public String toString()
{
return String.valueOf(element);
}
}
}