Java反转链表测试过程介绍

导读

本文主体为单项链表和双向链表的反转以及简单的测试，以便于理解链表相关的算法题目。

链表

特点

• 便于增删数据，不便于寻址

• 在内存中属于跳转结构

单链表和双链表的定义

单链表： 值，一条next指针

双链表：值，一条last指针，一条next指针

单向链表

Node结点

public static class Node {
   public int value;
   public Node next;
   public Node(int value) {
       this.value = value;
   }
   @Override
   public String toString() {
       ArrayList<Integer> nums = new ArrayList<>();
       Node node = this;
       while (node != null) {
           nums.add(node.value);
           node = node.next;
       }
       return nums.toString();
   }
}

反转单向链表

public static Node reverseLinkedList(Node head) {
   Node next = null;
   Node pre = null;
   while (head != null) {
       next = head.next;
       head.next = pre;
       pre = head;
       head = next;
   }
   return pre;
}

测试函数

public static void main(String[] args) {
   Node node = new Node(1);
   node.next = new Node(2);
   node.next.next = new Node(3);
   node = reverseLinkedList(node);
   System.out.println(node);
}

输出结果如下：

[3, 2, 1]

双向链表

Node结点

public static class DoubleList {
   public int value;
   public DoubleList next;
   public DoubleList last;
   public DoubleList(int value) {
       this.value = value;
   }
   @Override
   public String toString() {
       ArrayList<Integer> nums = new ArrayList<>();
       DoubleList node = this;
       while (node != null) {
           nums.add(node.value);
           node = node.next;
       }
       return nums.toString();
   }
}

反转双向链表

public static DoubleList reverseDoubleList(DoubleList head) {
   DoubleList next;
   DoubleList pre = null;
   while (head != null) {
       next = head.next;
       head.next = pre;
       // 注意和单项链表不一样的地方只有这一行，其他都基本一样
       head.last = next;
       pre = head;
       head = next;
   }
   return pre;
}

测试代码

public static void main(String[] args) {
   DoubleList node1 = new DoubleList(1);
   node1.next = new DoubleList(2);
   node1.next.last = node1;
   node1.next.next = new DoubleList(3);
   node1.next.next.last = node1.next;
   System.out.println("reverseDoubleList(node1) = " + reverseDoubleList(node1));
}

输出结果如下：

reverseDoubleList(node1) = [3, 2, 1]

来源：https://blog.csdn.net/weixin_46178937/article/details/127930618