本文为大家分享了java实现链表反转的具体代码，供大家参考，具体内容如下
算法题： 实现链表的反转
提供了2种方法，迭代法、递归法。
（为了方便输出可视化，在自定义的ListNode中重写了toString方法。）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
/** * 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实现链表反转的三种方式
分别通过栈、递归、指针的方式实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
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; } } } |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/kqZhu/article/details/119719751