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