public class Test {
public static void main(String[] args) {
try{
LinkList list1 = new LinkList()
LinkList list2 = new LinkList()
LinkList list3 = null
list1.addAt(0, new Item(1, 5))
list1.addAt(1, new Item(-1.5, 3))
list1.addAt(2, new Item(1, 1))
list2.addAt(0, new Item(0.5, 5))
list2.addAt(1, new Item(0.5, 4))
list2.addAt(2, new Item(1.5, 3))
list2.addAt(3, new Item(3, 0))
list3 = mergeLinkList(list1, list2)
System.out.println("一元多项式的相加过程：")
list1.listAll()
System.out.println(" + ")
list2.listAll()
System.out.println(" = ")
list3.listAll()
}
catch(Exception e){
e.printStackTrace()
}
}
/**
* 一元多项式的一般项类
*/
class Item{
private double coef //一元多项式的一般项的系数
private int exp //一元多项式的一般项的指数
public Item(){
this.coef = 0.0
this.exp = 0
}
public Item(double coef, int exp){
this.coef = coef
this.exp = exp
}
public double getCoef(){
return this.coef
}
public void setCoef(double coef){
this.coef = coef
}
public int getExp(){
return this.exp
}
public void setExp(int exp){
this.exp = exp
}
}
/**
*/
class Node{
private Item data
private Node next //链表结点的指针域，指向直接后继结点
public Node(){
data = null
next = null
}
public Node(Item data, Node next){
this.data = data
this.next = next
}
public Item getData(){
return this.data
}
public void setData(Item data){
this.data = data
}
public Node getNext(){
return this.next
}
public void setNext(Node next){
this.next = next
}
}
/**
* 链表类
*/
class LinkList{
private Node head = null//头结点指针
private int size = 0
public LinkList(){
head = new Node()
size = 0
}
//在i位置插入元素elem
public boolean addAt(int i, Item elem) {
if(i <0 || i >size){
return false
}
Node pre,curr
int pos
for(pre=headi>0 &&pre.getNext()!=nulli--,pre=pre.getNext())
curr = new Node(elem, pre.getNext())
pre.setNext(curr)
size++
return true
}
//删除i位置的元素
public boolean removeAt(int i) {
if(i <0 || i >= size){
return false
}
Node pre,curr
for(pre=headi>0 &&pre.getNext()!=nulli--,pre=pre.getNext())
curr = pre.getNext()
pre.setNext(curr.getNext())
size--
return true
}
java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。例如这样的链表：A->B->C->D->B->C->D，
当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1)
=
(D+S-1)*(D+S)/2
，
可以简单地理解成
O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。
方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。
这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1),
所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。
方法三：首先创建两个指针1和2（在Java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。
此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。
Java语言中的对象引用实际上是一个指针（这里的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
private static class Entry<E> {
E element // 当前存储元素
Entry<E> next // 下一个元素节点
Entry<E> previous // 上一个元素节点
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element
this.next = next
this.previous = previous
}
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
链表的数据结构我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。
存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点，因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。如何得到当前结点呢？我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。
例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
