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;

}

@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);

//方法需要替换

aEaXSMHalv 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 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();

http:// //反转，设置当前节点的下一个节点为前一个节点

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;

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。