数据结构----------单链表

/**
     * 向链表中添加节点（从链表尾部添加节点）
     *         如果链表为空，则链表的第一个节点的最后一个节点都指向新添加的节点
     *         如果链表不为空，将最后一个节点的next指向新产生的节点，并将新节点设为最后一个节点
     *         节点数加1
     * @param data
     */
    public void add(T data) {
        Node newNode = new Node(data);
        if(first == null) {//链表为空
            first = newNode;
            last = first;
        }else {//链表不为空
            last.next = newNode;
            last = newNode;
        }
        size++;//节点数加1
    }
    

/**
     * 从链表头部添加元素
     * @param data
     */
    public void addAtHeader(T data) {
        Node newNode = new Node(data);
        if(first == null) {
            first = newNode;
            last = first;
        }else {
            newNode.next = first;
            first = newNode;
        }
        size++;
    }

/**
     * 删除头结点
     * @return
     */
    public T deleteFirst() {
        T data = first.data;
        first = first.next;
        size--;
        return data;
    }

/**
     * 删除指定位置的节点
     * @param index
     * @return
     */
    public T deleteNode(int index) {
        Node preCurrent = null;
        Node current = first;
        if(index == 0) {
            return deleteFirst();
        }
        int i = 0;
        while(i < index) {
            preCurrent = current;
            current = current.next;
            i++;
        }
        preCurrent.next = current.next;
        size--;
        return current.data;
    }
    

/**
     * 遍历打印所有节点
     */
    public void print(Node node) {
        Node current = node;
        int i = 0;
        while(current != null) {
            System.out.println("This is the "+i+"th Node："+current.data);
            current = current.next;
            i++;
        }
    }

/**
     * 遍历方法2： 链表实现Iterable接口，返回一个Iterator对象
     *         
     */
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node current = first;//内部维护一个当前节点对象
            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                Node returnNode = current;
                current = current.next;//小心
                return returnNode.data;
            }
            
        };
    }

/**
     * 
     * 从为到头遍历链表:递归实现
     * 也可采用栈，正向遍历压栈，循环完毕，弹栈输出
     */
    public void printFromLastToFirst() {
        reversePrint(first);
    }
    
    public void reversePrint(Node n) {
        if(n == null) {
            return;
        }
        reversePrint(n.next);
        System.out.println("Node: "+n.data);
    }

/**
     * 链表反转
     * 注：也可采用递归实现
     * @return：返回最后反转后链表的第一个节点
     */
    public Node reverseNode() {
        //注：当前节点指的是即将要添加到反转后链表的节点
        Node reverseHeader = null;//反转后链表的第一个节点
        Node current = first;//当前节点
        Node next = null;//原链表中当前节点的下一个节点
        Node before = null;//反转后链表的当前节点的 前一个节点
        while(current != null) {
            next = current.next;//保存当前节点的下一个节点
            if(reverseHeader == null) {//反转链表中的第一个节点
                reverseHeader = current;
                reverseHeader.next = null;
            }else {//反转链表的第一个以后的节点
                before = reverseHeader;
                reverseHeader = current;
                reverseHeader.next = before;
            }
            current = next;//将当前节点指向下一个节点
        }
        return reverseHeader;//返回反转后链表的头结点
    }
    

/**
     * 返回链表倒数第k个节点(实现1)
     *         1. 返回链表总长度，计算倒数第k个节点的索引
     *         2. 遍历并返回倒数第k个节点
     * @param index
     * @return
     */
    public T findLastNode1(int index) {
        Node returnNode = first;
        int k = size()-index;//k为要返回节点的索引
        if(k < 0) {
            throw new NullPointerException("链表长度越界 ");
        }
        for(int i = 0; i < k; i++) {
            returnNode = returnNode.next;
        }
        return returnNode.data;
    }
    

/**
     * 返回链表倒数第k个元素（实现2）
     *         倒数第k个元素和最后一个元素相差k-1，所以可以选择两个指针
     *         1. 将第一个指针从头结点移动k-1次，使头结点和这个节点相差k-1
     *         2. 同时移动两个节点，当该节点是最后一个节点时，头结点为倒数第k个节点
     * @param index
     * @return
     */
    public T findLastNode2(int index) {
        Node firstNode = first;
        Node lastNode = first;
        //lastNode向后移动k-1次
        for(int i = 0; i < index - 1; i++) {
            if(lastNode == null) {
                throw new NullPointerException("链表长度越界");
            }
            lastNode = lastNode.next;
        }
        //同时移动，指针lastNode为最后一个节点
        while(lastNode.next != null) {
            firstNode = firstNode.next;
            lastNode  = lastNode.next;
        }
        
        return firstNode.data;
        
    }

/**
     * 合并两个有序链表
     * @param head2 要合并的链表的头结点
     * @return 合并后的有序链表的头结点
     */
    public Node merge(Node head2) {
        Node head1 = this.first;//当前链表的头结点
        if(head1 == null && head1 == null) 
            return null;
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        
        Node head = null;//新生成链表的头结点
        Node current = null;//新生成链表的当前节点
        while(head1 != null || head2 != null) {//至少一个链表没有循环完
            //1.为新生成的链表添加第一个节点
            if(head == null) {
                if(head1.data.compareTo(head2.data) < 0) {
                    head = head1;
                    current = head;
                    head1 = head1.next;
                }else {
                    head = head2;
                    current = head;
                    head2 = head2.next;
                }
            }
            //2.为生成的节点添加后续节点
            //如果head1为空，直接将当前节点指向head2，返回head即可
            if(head1 == null) {
                current.next = head2;
                return head;
            }
            //如果head2为空，直接将当前节点指向head1，返回即可
            if(head2 == null) {
                current.next = head1;
                return head;
            }
            //如果两个节点都不为空，进行比较，比较后继续循环
            if(head1.data.compareTo(head2.data) < 0) {
                current.next = head1;
                current = head1;
                head1 = head1.next;
            }else {
                current.next = head2;
                current = head2;
                head2 = head2.next;
            }
        }
        return head;
        
    }