java实现链表反转_生活百科

java实现链表反转,博智网带你了解详细信息。
本文为大家分享了java实现链表反转的具体代码，供大家参考，具体内容如下
算法题：实现链表的反转
提供了2种方法，迭代法、递归法。
（为了方便输出可视化，在自定义的ListNode中重写了toString方法。）
/** * Created By --- on 2021/8/12 * 以下代码可以直接粘贴进编译器输出 */public class ReverseList {public static void main(String[] args) {ListNode head = new ListNode(3, new ListNode(5, new ListNode(8, new ListNode(9))));System.out.println("初始链表：" + head);ListNode newList = reverseList(head);System.out.println("使用迭代法反转链表：" + newList);ListNode newList2 = reverseList2(null, newList);System.out.println("使用递归法反转链表：" + newList2);}/*** 迭代法*/public static ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;ListNode tmp;while (cur != null) {tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}/*** 递归法*/public static ListNode reverseList2(ListNode pre, ListNode cur) {if (cur == null) {return pre;}ListNode tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;return reverseList2(pre, cur);}}/** * singly-linked list */class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(String.valueOf(val));ListNode next = this.next;while (next != null) {sb.append(next.val);next = next.next;}return sb.toString();}}
输出结果：

文章插图

文章插图
再为大家分享一段java实现链表反转的三种方式
分别通过栈、递归、指针的方式实现：
import java.util.Stack; public class ReverseLinkedList {public static void main(String[] args) {ReverseLinkedList reverseLinkedList = new ReverseLinkedList();reverseLinkedList.test();}public void test() {Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);node1.setNext(node2);node2.setNext(node3);//方法需要替换node1 = reverseByPointer(node1);while (node1 != null) {System.out.println(node1.val);node1 = node1.getNext();}}//栈实现private Node reverseByStack(Node head) {if (head == null || head.getNext() == null) {return head;}Stack<Node> stack = new Stack<>();while (head != null) {stack.push(head);head = head.getNext();}head = stack.pop();Node tmp = head;while (!stack.empty()) {Node node = stack.pop();node.setNext(null);tmp.setNext(node);tmp = node;}return head;}//递归实现private Node reverseByRecursion(Node head) {if (head == null || head.getNext() == null) {return head;}//递归获取当前节点的后一个节点Node tmp = reverseByRecursion(head.getNext());Node node = head.getNext();head.setNext(null);node.setNext(head);return tmp;}//指针实现private Node reverseByPointer(Node head) {if (head == null || head.getNext() == null) {return head;}//pre指针指向前一个节点，初始第一个节点的前节点为空Node pre = null;//tmp指针指向当前节点Node tmp = null;while (head != null) {//tmp指针指向head头指针节点tmp = head;//head头指针向后遍历head = head.getNext();//反转，设置当前节点的下一个节点为前一个节点tmp.setNext(pre);//pre指针向后移动，指向当前节点pre = tmp;}return tmp;}private class Node {private int val;private Node next;public Node(int val) {this.val = val;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}}}
【java实现链表反转】以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持趣讯吧。