Java怎么实现链表的反转

这篇文章主要讲解了“Java怎么实现链表的反转”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java怎么实现链表的反转”吧！

创新互联建站服务项目包括环县网站建设、环县网站制作、环县网页制作以及环县网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，环县网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到环县省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

import java.util.ArrayList;
import java.util.Stack;

    /**
     * 链表的反转
     */
public class ReverseLinkedList {

/**
 * 非递归地反转链表：
 *
 *  特点：没有进行节点间的两两反转，而是采用依次插入到新链表的方式来实现反转。
 *
 *  过程：遍历一次链表，将遍历的节点依次插入到新链表的头部即可实现链表的反转。
 *
 *  复杂度：时间复杂度为O(N),辅助的空间复杂度为O(1)
 *
 * [@param](https://my.oschina.net/u/2303379) head
 *
 * [@return](https://my.oschina.net/u/556800) 将反转后的新链表的头节点返回。
 */
public static Node reverseByInsertToNewList(Node head) {

    Node current = head; // 正在遍历的节点
    Node next = null;    // 下一个要遍历的节点
    Node newHead = null; // 新链表头节点的引用(指向新链表头节点的指针)

    while (null != current) {

        next = current.next; // 将下一个要遍历的节点暂存起来

        /**
         * 将当前节点放到新链表的头部：
         *    1>将当前节点指向新链表的头部
         *    2>更新newHead
         */
        current.next = newHead;
        newHead = current;

        current = next; // 向后继续遍历
    }

    return newHead;
}


/**
 * 递归地反转链表：
 *
 *  特点：从后往前两两反转。
 *
 *  过程：递归地将当前节点(current)和它的后继节点(current.next)反转。
 *
 *  注意：
 *      1)最后一个节点没有后继节点，故最后一个节点不需要进行反转操作，只需将最后一个节点(作为新链表的头节点)直接返回即可。
 *      2)当前节点为链表倒数第二个节点时，开始第一次的反转操作。
 *      3)每次的反转操作都不会对新链表的头节点造成影响，只是将新的头结点返回而已。
 *
 *  解析：
 *      1)将 A->B->C->D 反转的操作可以分为：
 *          1>将 C->D 反转 ==> A->B->C  D->C->null
 *          2>将 B->C 反转 ==> A->B     D->C->B->null
 *          3>将 A->B 反转 ==>          D->C->B->A->null
 *
 *      2)将 A->B 反转的操作：
 *          1>将B的后继节点指向A，      即 B.next = A    即 A.next.next = A
 *          2>将A的后继节点设为null，   即 A.next = null
 *
 * [@param](https://my.oschina.net/u/2303379) current
 *
 * [@return](https://my.oschina.net/u/556800) 将反转后的新链表的头节点返回。
 */
private static Node reverseByRecursion(Node current) {

    if (null == current) {      // 若该链表为空链表，则直接返回
        return current;
    }

    if (null == current.next) { // 当前结点是尾结点时，直接返回。注：链表的尾节点即新链表的头节点
        return current;
    }

    Node newHead = reverseByRecursion(current.next); // newHead是链表的尾节点，即新链表的头节点。

    // 反转操作：将current和current.next进行反转，即：将当前节点放到新链表的尾部，故在递归的过程中新链表的头部不会变。
    current.next.next = current;
    current.next = null;

    // 将新链表的头节点返回。
    return newHead;
}


// -------

/**
 * 利用栈的先进后出特性来完成链表的反转。
 *
 * 时间复杂度为O(N),辅助的空间复杂度也为O(N)
 *
 * [@param](https://my.oschina.net/u/2303379) head
 * @return 将反转后的新链表的头节点返回。
 */
public static Node reverseWithStack(Node head) {

    Stack stack = new Stack();
    while (null != head) {
        stack.push(head);
        head = head.next;
    }
    return stack.peek();
}


/**
 * 反转双向链表
 *
 *  复杂度：时间复杂度为O(N),辅助的空间复杂度为O(1)
 *
 * @param head
 * @return 将反转后的新链表的头节点返回。
 */
public static Node reverseBidirectionalList(Node head) {

    if (null == head) { // 若该链表为空链表，则直接返回
        return null;
    }

    Node current = head;
    Node next = null;
    Node newHead = null;

    while (null != current) {

        // 反转
        next = current.next;    // 将当前节点的后继节点暂存起来
        current.next = current.prev;
        current.prev = next;

        if (null == next) {     // 若下一个要遍历的节点为null，则说明已经到达链表的尾部，此时current即链表的尾节点
            newHead = current;
        }

        current = next;         // 继续向后遍历
    }

    return newHead;
}


// -------

/**
 * 将链表从头到尾依次打印出来
 *
 * @param head
 */
public static void print(Node head) {

    ArrayList