算法-反转单向链表

需求

思路

• 链表必有节点，节点两要素：当前元素值，下一个节点地址

import java.util.Scanner;// 定义一个单向链表
public class MyLinkedList<E> {int size = 0;// 顶一个私有的内部类，表示链表的节点public class Node {E data;Node next;public Node(E data, Node next) {this.data = data;this.next = next;}}
}

添加节点

• 第一次插入直接插入头结点
• 后面都使用尾插法，插入到最后一个元素的后面（所以需要一个一个遍历）

// 添加节点
public Node add(E e) {Node head = null;Scanner scanner = new Scanner(System.in);while (true) {System.out.println("请输入数据，输入exit退出");String data = scanner.next();if (data.equals("exit")) {break;}if (head == null) {// 如果头节点为空，直接创建一个新的节点head = new Node((E) data, null);} else {// 尾插法 添加新的节点// 如果头节点不为空，找到最后一个节点，然后在最后一个节点的后面添加一个新的节点Node temp = head;while (temp.next != null) {temp = temp.next;}// 在最后一个节点的后面添加一个新的节点temp.next = new Node((E) data, null);}size++;}return head;
}

遍历

// 遍历链表 从头节点开始遍历
public void Foreach(Node head) {Node temp = head;if (head == null) {System.out.println("链表为空");return;}while (temp != null) {System.out.println(temp.data + " ");temp = temp.next;}
}

链表指定位置反转

• 下标异常直接返回头结点
• 先找到left的前一个节点，方便下次重置的时候直接找到left
• 将left和right之间的内容存储到一个数组中
• 对数组的内容进行折半反转
• 遍历left到right节点，将反转之后的内容替换进去

  // 链表反转(不一定要反转节点，反转节点的内容也可以)public Node reverse(Node head,int left,int right) {if (head == null ||left < 1 || left > size || right < 1 || right > size || left >= right) {return head;}//1. 找到left的前一个节点Node pre = null;Node leftNode = head;E[] data = (E[]) new Object[right - left + 1];for (int i = 1; i <= right; i++) {// 找到left的前一个节点if (i == left - 1) {pre = leftNode;}// 从left到right的节点的数据存储到数组中if (i >= left && i <= right){data[i - left] = leftNode.data;}// leftNode指向下一个节点leftNode = leftNode.next;}//2. 找到right的后一个节点Node rightNode = leftNode;// 3.反转data数组for (int i = 0; i < data.length / 2; i++) {E temp = data[i];data[i] = data[data.length - i - 1];data[data.length - i - 1] = temp;}// 4.从pre节点开始，将data数组中的数据赋值给链表中的节点for (int i = 0; i < data.length; i++) {pre.next.data = data[i];pre = pre.next;}return head;}

测试：

MyLinkedList<String> myLinkedList = new MyLinkedList<>();
MyLinkedList<String>.Node head = myLinkedList.add("aa");
myLinkedList.Foreach(head);
myLinkedList.reverse(head,2,4);
System.out.println("反转后的链表");
myLinkedList.Foreach(head);

• 反转前的链表：aa bb cc dd ee ff gg
• 反转后的链表：aa dd cc bb ee ff gg