输入一个链表,反转链表后,输出新链表的表头。
递归法
public class RevnNode {
public static class Node {
public int value;
public Node nextNode;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
public Node(int value) {
this.value = value;
}
}
/**
* 反转操作方法1 递归实现:从最后一个Node开始,在弹栈的过程中将指针顺序置换的。
*
* @param head
* @return
*/
public static Node reverse1(Node head) {
if (head == null || head.nextNode == null)
return head;
Node temp = head.nextNode;
Node newHead = reverse1(head.nextNode);
temp.nextNode = head;
head.nextNode = null;
return newHead;
}
/**
* 反转操作方法2 :在链表遍历的过程中将指针顺序置换
* @param node
* @return
*/
public static Node reverse2(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
next = node.nextNode;
node.nextNode = pre;
pre = node;
node = next;
}
return pre;
}
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
head.setNextNode(node1);
node1.setNextNode(node2);
node2.setNextNode(node3);
// 打印反转前的链表
Node h = head;
while (null != h) {
System.out.print(h.getValue() + " ");
h = h.getNextNode();
}
// 调用反转方法1
System.out.println("\n*********** reverse1 ***************");
head = reverse1(head);
// 打印反转后的结果
while (null != head) {
System.out.print(head.getValue() + " ");
head = head.getNextNode();
}
// 调用反转方法2
System.out.println("\n*********** reverse2 ***************");
head = reverse2(head);
// 打印反转后的结果
while (null != head) {
System.out.print(head.getValue() + " ");
head = head.getNextNode();
}
}
}