链表反转的实现可以用两种方式:遍历法和递归法,最终的效果如下:
原始链表:->30->25->20->15->10->5
反转后的链表:->5->10->15->20->25->30
遍历法过程如下:
while(currNode!=null){
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
实现过程如下图:
实现代码如下:
public class ReverseLinkedList {
public static void main (String[] args) throws java.lang.Exception
{
LinkedListT a = new LinkedListT();
a.addAtBegin(5);
a.addAtBegin(10);
a.addAtBegin(15);
a.addAtBegin(20);
a.addAtBegin(25);
a.addAtBegin(30);
a.display(a.head);
a.reverseIterative(a.head); }
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedListT{
public Node head;
public LinkedListT(){
head=null;
}
public void addAtBegin(int data){
Node n = new Node(data);
n.next = head;
head = n;
}
public void reverseIterative(Node head){
Node currNode = head;
Node nextNode = null;
Node prevNode = null;
while(currNode!=null){
nextNode = currNode.next;
currNode.next = prevNode;//反转:使链表的下一个节点和上一个节点相连
prevNode = currNode;//保存反转后的链表
currNode = nextNode;
}
head = prevNode;
System.out.println("\n Reverse Through Iteration");
display(head);
}
public void display(Node head){
//
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
}
递归法过程如下:
实现过程如下图:
实现代码如下:
public class ReverseLinkedList {
public static void main (String[] args) throws java.lang.Exception
{
LinkedListT a = new LinkedListT();
a.addAtBegin(5);
a.addAtBegin(10);
a.addAtBegin(15);
a.addAtBegin(20);
a.addAtBegin(25);
a.addAtBegin(30);
a.display(a.head);
a.reverseRecur(a.head);
}
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedListT{
public static Node head=null;
public LinkedListT(){
head=null;
}
public void addAtBegin(int data){
Node n = new Node(data);
n.next = head;
head = n;
}
public Node reverseRecur(Node current){
if(current==null){
return null;
}
if(current.next==null){
head = current;
return null;
}
reverseRecur(current.next);
current.next.next = current;
current.next = null;
return head;
}
public void display(Node head){
//
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
}