Java怎么实现链表的反转

65次阅读
没有评论

共计 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 小编将为大家推送更多相关知识点的文章,欢迎关注!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-16发表,共计3708字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)