单链表的一些主要功能：

• 1.单链表

// node类
 public class Node {
     public Object data;
     public Node next;

     // 构造方法要公开
     public Node(Object data, Node next){
         this.data = data;
         this.next = next;
     }
     public Node(Object data) {
         this.data = data;
         this.next = null;
     }
     public Node() {}

     @Override
     public String toString() {
         return "Node{data:" + data + "}";
     }
 }

// linkedlist类

public class LinkedList {
    public Node head;

    public LinkedList() {
        this.head = null;
    }

    // 插入
    // 默认插入到链表尾
    public void add(Node node) {
        // 空
        if(head == null){
            head = node;
        } else {
            // 非空
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    // 插入到指定位置
    public void add(Node node, int position) {
        int length = getLength();
        // 只允许0 - length 之间，可以考虑负数倒序
        if(position > length || position < 0) {
            throw new IndexOutOfBoundsException();
        }
        if(position == 0){
            // 插入到头
            node.next = head;
            head = node;
        } else{
            int count;
            Node cur = head;
            for(count = 1; count < position; count ++) {
                cur = cur.next;
            }
            node.next = cur.next;
            cur.next = node;
        }
    }

    // 删除指定位置的节点
    public void delete(int position){
        int length = getLength();
        if(position >= length || position < 0) {
            throw new IndexOutOfBoundsException();
        }
        if(position == 0){
            head = head.next;
        } else{
            int count;
            Node cur = head;
            for(count = 1; count < position; count ++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
    }
    // 得到指定位置的节点
    public Node get(int position){
        int length = getLength();
        if(position >= length || position < 0){
            throw new IndexOutOfBoundsException();
        }
        if(position == 0){
            return head;
        }
        int count;
        Node cur = head;
        for(count = 0;count < position; count ++){
            cur = cur.next;
        }
        return cur;
    }
    // 打印
    public void print() {
        Node cur = head;
        System.out.print("[ ");
        while (cur != null) {
            System.out.print(cur.data.toString() + " ");
            cur = cur.next; // 更新
        }
        System.out.println("]");
    }

    // 判空
    private boolean isEmpty() {
        return head == null; // 只要头空就是空
    }
    // 长度
    public int getLength(){
        int count = 0;
        if(head == null){
            return count;
        }
        Node cur = head;
        count ++;
        while(cur.next != null){
            cur = cur.next;
            count ++;
        }
        return count;
    }
    // 表尾
    public Node getTail(){
        Node cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        return cur;
    }
    // 串联
    public LinkedList concat(LinkedList linkedList){
        Node tail = getTail();
        tail.next = linkedList.head;
        return this;
    }
    // 逆序(迭代循环实现)
    public void reverse(){
        Node cur = head;
        Node pre = null;
        while (cur != null){
            head = cur.next; // 移头
            cur.next = pre; // 回指
            pre = cur; // 更新pre
            cur = head; // 更新cur
        }
        head = pre;
    }
    // 逆序(递归实现)
    public void reverse(Node node){
        if (node == null || node.next == null){
            // 尾节点,正向截止条件
            head = node;
        } else{
            reverse(node.next); // 递归
            node.next.next = node; // 回溯，逆序
            node.next = null; // 回溯截止条件
        }
    }
}

• 2.单链表实现多项式相加

 // ----- polynomial ------------------------------------------------------
        // 8x^8 + 54x^7 + 7x^6 + 1x^4 + 3x^3 + 4x + 2
        LinkedList polyA = new LinkedList();
        int[] polyA_const = { 8, 54, 7, 1, 3, 4, 2 };
        int[] polyA_exp = { 8, 7, 6, 4, 3, 1, 0 };
        for(int i = 0; i < polyA_const.length; i ++){
            polyA.add(new Node(new Polynomial(polyA_exp[i], polyA_const[i])));
        }
        polyA.print();
        // polyA.reverse(polyA.head);
        // polyA.print();
        // -2x^9 + 6x^8 + 5x^4 + 6x^3 + 8x^2 + 6x + 9
        LinkedList polyB = new LinkedList();
        int[] polyB_const = { -2, 6, 5, 6, 8, 6, 9 };
        int[] polyB_exp = { 9, 8, 4, 3, 2, 1, 0 };
        for(int j = 0; j < polyA_const.length; j ++){
            polyB.add(new Node(new Polynomial(polyB_exp[j], polyB_const[j])));
        }
        polyA.print();
        polyB.print();
        // sum
        Node head_A = polyA.head;
        Node head_B = polyB.head;
        LinkedList sumList = new LinkedList();
        while(head_A != null){
            while(head_B != null){
                // 都不是尾节点
                Polynomial polynomial_A = (Polynomial)(head_A.data);
                Polynomial polynomial_B = (Polynomial)(head_B.data);
                if(polynomial_A.getExponent() < polynomial_B.getExponent()){
                    sumList.add(new Node(polynomial_B));
                    head_B = head_B.next;
                }else
                if(polynomial_A.getExponent() == polynomial_B.getExponent()){
                    sumList.add(new Node(new Polynomial(polynomial_A.getExponent(), polynomial_A.getConstant() + polynomial_B.getConstant())));
                    head_B = head_B.next;
                    head_A = head_A.next;
                }else if(polynomial_A.getExponent() > polynomial_B.getExponent()) {
                    sumList.add(new Node(polynomial_A));
                    head_A = head_A.next;
                }
            }
        }
        sumList.print();


// 多项式类
class Polynomial {
    private int exponent;
    private int constant;

    public Polynomial(int exponent, int constant) {
        this.exponent = exponent;
        this.constant = constant;
    }

    public int getExponent() {
        return exponent;
    }

    public void setExponent(int exponent) {
        this.exponent = exponent;
    }

    public int getConstant() {
        return constant;
    }

    public void setConstant(int constant) {
        this.constant = constant;
    }

    @Override
    public String toString() {
        return "{" + constant + "^" + exponent + "}";
    }
}