节点类:
class="java" name="code">
//节点类
class Node{
public Node(int value){
this.value = value;
}
public Node(){
}
int value;
Node next;
}
初始化链表
//初始化一个有序的单链表
public Node initList(){
Node head = new Node();
Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
n1.value = 1;
n2.value = 2;
n3.value = 3;
n4.value = 4;
n5.value = 5;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
head.next = n1;
return head;
}
非
递归的逆转
//单链表逆转,非递归
public Node reverseList(Node node){
if (null == node) {
return node;
}
//上一个节点
Node upper = null;
//当前节点
Node cur = node.next;
//下一个节点
Node next = null;
while (null != cur) {
next = cur.next;
cur.next = upper;
upper = cur;
cur = next;
}
//反转结束后,upper引用指向原链表的最后一个节点,即反转后的第一个节点
node = upper;
return node;
}
递归的逆转
public Node reverse(Node node){
if(node==null || node.next == null)return node;
Node next = node.next;
//将node的next清空,否则在递归return到最上层时要逆转的原链表的最后一个节点的next会指向原来的头节点,而原来的头节点的next又指向原来的第一个节点,即逆转后的最后一个节点,会造成无限的重复链表
node.next = null;
Node returnNode = reverse2(next);
next.next = node;
return returnNode;
}
打印链表:
//打印单链表
public void printList(Node head){
String str = "";
for(Node n = head;n!=null;){
str = str + " " + n.value;
n = n.next;
}
System.out.println(str);
}
调用:
Test t = new Test();
Node head = t.initList();
System.out.println("逆转前:");
t.printList(head.next);
System.out.println("逆转后:");
t.printList(t.reverseList(head));