这篇文章主要讲解了“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怎么实现链表的反转这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/1399755/blog/1802519