这篇文章主要讲解了“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<Node> stack = new Stack<Node>(); 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<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; } 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怎么实现链表的反转这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。