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; } @Override public 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;} }}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持好吧啦网。