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);        //方法需要替换        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;        }    }}

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