Java实现单向链表反转

作者:袖梨 2022-11-14

本文实例为大家分享了Java实现单向链表反转的具体代码,供大家参考,具体内容如下

1、实现代码

public class LinkedListTest {

  public static void main(String[] args) {
    Node A = new Node("A");
    Node B = new Node("B");
    Node C = new Node("C");
    Node D = new Node("D");
    Node E = new Node("E");
    Node F = new Node("F");
    A.next = B;
    B.next = C;
    C.next = D;
    D.next = E;
    E.next = F;
    print(A);

    LinkedListReversor reversor = LinkedListReversor.RECURSION;
    System.out.println(reversor.getStrategy() + ":");
    Node tmp = reversor.execute(A);
    print(tmp);

    reversor = LinkedListReversor.NO_RECURSION;
    System.out.println(reversor.getStrategy() + ":");
    print(reversor.execute(tmp));
  }

  private static void print(Node node) {
    while (node != null) {
      System.out.print(node.value);
      node = node.next;
      if (node != null) {
        System.out.print("->");
      } else {
        System.out.println();
      }
    }
  }

}

class Node {
  public String value;
  public Node next;

  public Node(String value) {
    this.value = value;
  }
}

enum LinkedListReversor {
  RECURSION("递归") {
    @Override
    public Node execute(Node node) {
      Node prev = null;
      if (node == null || node.next == null) {
        prev = node;
      } else {
        Node tmp = execute(node.next);
        node.next.next = node;
        node.next = null;
        prev = tmp;
      }
      return prev;
    }
  },
  NO_RECURSION("非递归") {
    @Override
    public Node execute(Node node) {
      Node prev = null;
      while (node != null) {
        Node tmp = node;
        node = node.next;
        tmp.next = prev;
        prev = tmp;
      }
      return prev;
    }
  };
  private String strategy;

  private LinkedListReversor(String strategy) {
    this.strategy = strategy;
  }

  public abstract Node execute(Node node);

  public String getStrategy() {
    return strategy;
  }
}

2、实现思路

递归:从尾部开始处理

非递归:从头部开始处理

相关文章

精彩推荐