[Java算法系列教程]-单链表反转
要求很简单,输入一个链表,反转链表后,输出新的链表。
首先定义Node:
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
递归法
递归法是从最后一个Node开始,在弹栈的过程中将指针顺序置换
public Node reverse(Node head) {
if (head == null || head.next == null)
return head;
Node temp = head.next;
Node newHead = reverse(head.next);
temp.next = head;
head.next = null;
return newHead;
}
遍历法
遍历法就是在链表遍历的过程中将指针顺序置换
public static Node reverse(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
}