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 java.util.HashSet;
import java.util.Set;
import org.apache.commons.io.IOUtils;
//
public class LinkedList2<T>
{
public static void main(String[] args) throws CloneNotSupportedException
{
LinkedList2<Integer> list = new LinkedList2<Integer>(1, 2, 3, 4, 5);
// System.out.println(list.isEmpty());
// System.out.println(list.size());
// System.out.println(list.createEntry(1).next);
// System.out.println(list.getEntry(-1));
// System.out.println(list.getEntry(0));
// System.out.println(list.getEntry(2));
System.out.println(list);
// LinkedList2<Integer> n_list = (LinkedList2<Integer>) list.clone();
// System.out.println(n_list);
// LinkedList2.reverseListByIterator(n_list);
// LinkedList2.reverseListByRecursion(n_list);
// System.out.println(n_list);
// Entry<Integer> entry = LinkedList2.lastIndexOf(list, 2);
// Entry<Integer> entry = LinkedList2.lastIndexOfByArray(list, 5);
// Entry<Integer> entry = LinkedList2.getMiddleEntry(list);
// System.out.println(entry == null ? "not found" : entry.element);
// LinkedList2.reversePrintListByStack(list);
// LinkedList2.reversePrintListByRecursion(list);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 2, 2, 5);
// LinkedList2<Integer> list2 = new LinkedList2<Integer>(2, 3, 3, 3, 4);
// System.out.println(list1);
// System.out.println(list2);
// LinkedList2<Integer> n_list = LinkedList2.mergeList(list1, list2);
// System.out.println(n_list);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3);
// Entry<Integer> lastEntry = list1.getEntry(list1.size() - 1);
// Entry<Integer> firstEntry = list1.getEntry(0);
// lastEntry.next = firstEntry;
// System.out.println(LinkedList2.hasLoop(list1));
// Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry(list1);
// Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry2(list1);
// System.out.println(entry == null ? "no loop" : entry.element);
// LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4);
// LinkedList2<Integer> list2 = new LinkedList2<Integer>(11, 22, 33,
// 44);
// // list2.getEntry(2).setNext(list1.getEntry(1));
// list2.getEntry(3).setNext(list1.getEntry(3));
// System.out.println(list1);
// System.out.println(list2);
// System.out.println(LinkedList2.isIntersect(list1, list2));
// System.out.println(LinkedList2.isIntersect2(list1, list2));
// System.out.println(LinkedList2.isIntersect3(list1, list2));
//
// Entry<Integer> entry = LinkedList2.getFirstIntersectEntry(list1,
// list2);
// System.out.println(entry == null ? "not found" : entry.element);
// LinkedList2.deleteEntry(list, list.getEntry(4));
// System.out.println(list);
LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4, 2, 3, 4, 5, 1);
System.out.println(list1);
LinkedList2.deleteDuplicateEntries(list1);
System.out.println(list1);
}
//
private Entry<T> head;
public LinkedList2()
{
// ，
head = new Entry<T>(null);
}
public LinkedList2(T... elements)
{
this();
// ,
Entry<T> tail = head;
for (T element : elements)
{
// ,next null
Entry<T> newEntry = new Entry<T>(element, null);
// next
tail.next = newEntry;
//
tail = newEntry;
}
}
public void setHead(Entry<T> head)
{
this.head = head;
}
public boolean isEmpty()
{
// next ，
return head.next == null;
}
// 1.
public int size()
{
if (isEmpty())
return 0;
Entry<T> curEntry = head.next;
int c = 0;
while (curEntry != null)
{
c++;
curEntry = curEntry.next;
}
return c;
}
// 2. : reverseList（ ）
public static <T> void reverseListByIterator(LinkedList2<T> list)
{
Entry<T> curEntry = list.head.next; //
Entry<T> nextEntry = null; //
Entry<T> nextnextEntry = null; //
// ，
if (curEntry == null || curEntry.next == null)
return;
// :
// head -> first -> second -> third .. -> null
// [cur] [next] [nextnext]
// ：
// head -> second -> first -> third .. -> null
// [next] [cur] [nextnext]
// ................
// ，
while (curEntry.next != null)
{
//
nextEntry = curEntry.next;
//
nextnextEntry = nextEntry.next;
// next
nextEntry.next = list.head.next;
// next
list.head.next = nextEntry;
// next
curEntry.next = nextnextEntry;
}
}
// 2. : reverseListRec（ ）
public static <T> void reverseListByRecursion(LinkedList2<T> list)
{
// ， ，
if (list.head.next == null || list.head.next.next == null)
return;
list.head.next = reverseList(list.head.next);
}
private static <T> Entry<T> reverseList(Entry<T> head)
{
// 1 -> 2 -> 3 -> 4 -> null
// head 4 -> null, head
// ,head 3 -> 4 - > null, head newHead
//newHead -> 4 -> null ↓ - - ↑
// head.next.next = head newHead -> 4 - > 3
// head.next = null , newHead -> 4 - > 3 -> null
//.........
// ，
if (head.next == null)
return head;
// ， （ ），
Entry<T> newHead = reverseList(head.next);
// next
head.next.next = head;
// next null
head.next = null;
return newHead;
}
// 3. K （k > 0）
public static <T> Entry<T> lastIndexOf(LinkedList2<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The number should be greater than zero");
// n ， first
Entry<T> first = list.getEntry(n - 1);
//second
Entry<T> second = list.head;
//first second ,
while (first != null)
{
first = first.next;
second = second.next;
}
// second n
return second;
}
// 3. K （k > 0）,
@SuppressWarnings("unchecked")
public static <T> Entry<T> lastIndexOfByArray(LinkedList2<T> list, int n)
{
if (n <= 0)
throw new IllegalArgumentException("The number should be greater than zero");
Object[] entries = new Object[n];
int c = 0, index = 0;
Entry<T> curEntry = list.head.next;
while (curEntry != null)
{
entries[index] = curEntry;
index = (index + 1) % n; // n
c++;
curEntry = curEntry.next;
}
if (entries[index] == null)
throw new IllegalStateException("Less than " + n + " elements, current is " + c);
return Entry.class.cast(entries[index]);
}
// 4.
public static <T> Entry<T> getMiddleEntry(LinkedList2<T> list)
{
if (list.isEmpty())
return null;
Entry<T> first = list.head;
Entry<T> second = list.head;
//first ，second ， first ，second
while (first != null && first.next != null)
{
first = first.next.next;
second = second.next;
}
return second;
}
// 5. ,
public static <T> void reversePrintListByStack(LinkedList2<T> list)
{
java.util.LinkedList<T> stack = new java.util.LinkedList<T>();
Entry<T> curEntry = list.head;
while (curEntry.next != null)
{
stack.push(curEntry.next.element);
curEntry = curEntry.next;
}
String result = "[";
while (!stack.isEmpty())
{
result += stack.pop();
result += ", ";
}
if (result.length() > 1)
result = result.substring(0, result.length() - 2);
result += "]";
System.out.println(result);
}
// 5. （ ）
public static <T> void reversePrintListByRecursion(LinkedList2<T> list)
{
String result = reversePrint(list.head);
if (result.length() > 0)
result = result.substring(0, result.length() - 2);
System.out.println("[" + result + "]");
}
private static <T> String reversePrint(Entry<T> entry)
{
if (entry.next == null)
return "";
String result = reversePrint(entry.next);
result += entry.next.element + ", ";
return result;
}
// 6. list1 list2 ，
@SuppressWarnings("unchecked")
public static <T> LinkedList2<T> mergeList(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
Entry<T> newHead = new Entry<T>(null);
Entry<T> preEntry = newHead;
while (curEntry1.next != null && curEntry2.next != null)
{
// entry1 element entry2 element， entry1
if (((Comparable) curEntry1.next.element).compareTo(curEntry2.next.element) < 0)
{
//
preEntry.next = new Entry<T>(curEntry1.next.element, null);
curEntry1 = curEntry1.next;
}
else
{
// ， entry2
preEntry.next = new Entry<T>(curEntry2.next.element, null);
curEntry2 = curEntry2.next;
}
preEntry = preEntry.next;
}
// list1 entry
while (curEntry1.next != null)
{
preEntry.next = new Entry<T>(curEntry1.next.element);
curEntry1 = curEntry1.next;
preEntry = preEntry.next;
}
// list2 entry
while (curEntry2.next != null)
{
preEntry.next = new Entry<T>(curEntry2.next.element);
curEntry2 = curEntry2.next;
preEntry = preEntry.next;
}
//
LinkedList2<T> result = new LinkedList2<T>();
result.setHead(newHead);
return result;
}
// 7.
public static <T> boolean hasLoop(LinkedList2<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
//first ，second ， first second ，
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(LinkedList2<T> list)
{
Entry<T> first = list.head;
Entry<T> second = list.head;
//first ，second ， first second ， ，
// ， first ，second ， ，
// first second ,
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(LinkedList2<T> list)
{
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
Entry<T> curEntry = list.head;
// map ， map ， ，
//
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(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
// list1 map
while (curEntry1.next != null)
{
storage.put(curEntry1.next, Boolean.TRUE);
curEntry1 = curEntry1.next;
}
// list2 ， map ， ，
//
while (curEntry2.next != null)
{
if (storage.get(curEntry2.next) == Boolean.TRUE)
return true;
curEntry2 = curEntry2.next;
}
return false;
}
// 9. next ，
public static <T> boolean isIntersect2(LinkedList2<T> list1, LinkedList2<T> list2)
{
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;
}
// list1 next null，
curEntry1.next = null;
return exist;
}
// 9.
public static <T> boolean isIntersect3(LinkedList2<T> list1, LinkedList2<T> list2)
{
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(LinkedList2<T> list1, LinkedList2<T> list2)
{
Entry<T> curEntry1 = list1.head;
Entry<T> curEntry2 = list2.head;
int m = 0, n = 0;
//
//m = list1.size();
while (curEntry1.next != null)
{
m++;
curEntry1 = curEntry1.next;
}
//
//n = list2.size()
while (curEntry2.next != null)
{
n++;
curEntry2 = curEntry2.next;
}
curEntry1 = list1.head;
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--;
}
}
// list1 list2
while (curEntry1 != null)
{
curEntry1 = curEntry1.next;
curEntry2 = curEntry2.next;
// entry
if (curEntry1 == curEntry2)
return curEntry1;
}
return null;
}
// 11. pHead pToBeDeleted，O(1) pToBeDeleted: delete
public static <T> void deleteEntry(LinkedList2<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 (list.head.next == entry)
list.head.next = null;
else
{
//
Entry<T> preEntry = list.head;
while (preEntry.next != null && preEntry.next != entry)
{
preEntry = preEntry.next;
}
if (preEntry.next == null)
throw new IllegalStateException("No element found " + entry);
preEntry.next = preEntry.next.next;
}
}
}
// 12.
public static <T> void deleteDuplicateEntries(LinkedList2<T> list)
{
Set<T> entries = new HashSet<T>();
Entry<T> curEntry = list.head;
while (curEntry.next != null)
{
if (entries.contains(curEntry.next.element))
curEntry.next = curEntry.next.next;
else
{
entries.add(curEntry.next.element);
curEntry = curEntry.next;
}
}
}
@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
{
LinkedList2<T> result = new LinkedList2<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();
}
}
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.next;
while (curEntry != null && c < index)
{
curEntry = curEntry.next;
c++;
}
if (curEntry == null)
throw new IllegalStateException("Less than " + (index + 1) + " elements, current is " + c);
return curEntry;
}
@Override
public String toString()
{
String result = "[";
Entry<T> curEntry = head.next;
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;
public void setElement(T element)
{
this.element = element;
}
public T getElement()
{
return element;
}
public void setNext(Entry<T> next)
{
this.next = next;
}
Entry(T element)
{
this(element, null);
}
Entry(T element, Entry<T> next)
{
this.element = element;
this.next = next;
}
@Override
public String toString()
{
return String.valueOf(element);
}
}
}