Shulou(Shulou.com)05/31 Report--

这篇文章主要讲解了"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 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 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;}public static void main(String[] args) { Node head = init(); print(head); // 反转单向链表// Node newHead = reverseByInsertToNewList(head);// Node newHead = reverseByRecursion(head); // 反转双向链表 Node newHead = reverseBidirectionalList(head); print(newHead); // 利用stack反转双向链表 Node newHeadByStack = reverseWithStack(head); printBidirectionList(newHeadByStack);}感谢各位的阅读，以上就是"Java怎么实现链表的反转"的内容了，经过本文的学习后，相信大家对Java怎么实现链表的反转这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.