本文为大家分享了java实现链表反转的具体代码，供大家参考，具体内容如下
算法题：实现链表的反转
提供了2种方法，迭代法、递归法。
（为了方便输出可视化，在自定义的ListNode中重写了toString方法。）
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);
}
}
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;
}
}
}以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程网。
