Java怎么实现链表的反转

共计 3708 个字符，预计需要花费 10 分钟才能阅读完成。

这篇文章主要讲解了“Java 怎么实现链表的反转”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“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;

 *  注意： * 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;

 * [@param](https://my.oschina.net/u/2303379) head
 * @return  将反转后的新链表的头节点返回。 */
public static Node reverseWithStack(Node head) {
 Stack Node  stack = new Stack Node 
 while (null != head) { stack.push(head);
 head = head.next;
 }
 return stack.peek();

 */
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;

 ArrayList Object  list = new ArrayList ();
 while (null != head.next) { list.add(head.value);
 head = head.next;
 }
 list.add(head.value);
 System.out.println(list.toString());
 *  将双向链表从尾到头依次打印出来
 *
 * @param tail
 */
public static void printBidirectionList(Node tail) { ArrayList Object  list = new ArrayList ();
 while (null != tail.prev) { list.add(tail.value);
 tail = tail.prev;
 }
 list.add(tail.value);
 System.out.println(list.toString());
 *  初始化链表
 *
 * @return
 */
public static Node init() { Node head = new Node(5);
 Node node1 = new Node(3);
 Node node2 = new Node(2);
 Node node3 = new Node(6);
 Node node4 = new Node(7);
 Node node5 = new Node(17);
 Node node6 = new Node(9);
 head.next = node1;
 node1.prev = head;
 node1.next = node2;
 node2.prev = node1;
 node2.next = node3;
 node3.prev = node2;
 node3.next = node4;
 node4.prev = node3;
 node4.next = node5;
 node5.prev = node4;
 node5.next = node6;
 node6.prev = node5;
 node6.next = null;
 return head;

 //  反转单向链表
// Node newHead = reverseByInsertToNewList(head);
// Node newHead = reverseByRecursion(head);
 //  反转双向链表
 Node newHead = reverseBidirectionalList(head);
 print(newHead);
 //  利用 stack 反转双向链表
 Node newHeadByStack = reverseWithStack(head);
 printBidirectionList(newHeadByStack);
}

感谢各位的阅读，以上就是“Java 怎么实现链表的反转”的内容了，经过本文的学习后，相信大家对 Java 怎么实现链表的反转这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！