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