链表的反转的三种方法
package com.javase.reverselink;
public class ReverseLink {
public static void main(String[] args) {
Node<Integer> head =buildLink();
Node<Integer> newNode =recursiveReverseLink(head);
print(newNode);
}
public static Node<Integer> reverseLink(Node<Integer> head){
//提前判断，如果链表的长度为0或1，则不需要反转
if(head==null||head.next==null){
return head;
}
//需要三个变量进行控制
Node<Integer> preNode =null;
Node<Integer> currentNode =head;
Node<Integer> nextNode = head.next;
//执行反转
currentNode.next = preNode;
//循环反转
while (nextNode!=null){
//整体移动
preNode =currentNode;
currentNode=nextNode;
nextNode=currentNode.next;
//执行反转
currentNode.next = preNode;
if(nextNode==null){
head=currentNode;
}
}
return head;
}
/**
* 使用递归的方式进行链表反转
* @param head 旧的链表的头结点
* @return 反转后的链表的头结点
*/
public static Node<Integer> recursiveReverseLink(Node<Integer> head){
//退出机制
if(head == null || head.next ==null){
return head;
}
//分成两个部分 1.一个结点 2、后边已经反转成功的链表
Node<Integer> newHead = recursiveReverseLink(head.next);
//核心的反转逻辑
head.next.next=head;
head.next=null;
return newHead;
}
public static Node<Integer> headInsertReserveLink(Node<Integer> head){
if(head==null||head.next==null){
return head;
}
Node<Integer> temp = null,newHead=null;
while(head!=null){
temp=head;
head=head.next;
temp.next=newHead;
newHead =temp;
}
return newHead;
}
/**
* 用来遍历打印链表的数据
* @param head
*/
public static void print(Node<Integer> head){
Node<Integer> current = head;
while(current!=null){
System.out.println(current.t);
current=current.next;
}
}
public static Node<Integer> buildLink(){
Node<Integer> head = new Node<>(1);
Node<Integer> node2 = new Node<>(2);
Node<Integer> node3 = new Node<>(3);
Node<Integer> node4= new Node<>(4);
Node<Integer> node5 = new Node<>(5);
head.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
return head;
}
private static class Node<T>{
private T t;
private Node<T> next;
public Node(T t){
this.t=t;
}
}
}