单链表反转（java版本）
- 第一种方法
- 第一步，判断节点是否为空，节点是否只有一个
- 第二步，设置currentNode记录为当前结点，secondNode记录下一个节点。当前节点指向为null
- 第三步，用第三方temp变量将secondNode指向的节点值保存起来。将secondNode节点指向currentNode。重置currentNode为secondNode,重置secondNode为temp。循环判断secondNode是否为null
- 第四步，返回currentNode，即最后一个节点
private static Node reverseMethodOne(Node node) {
// 顺序依次一个一个反转，设置变量temp记录变量
if (node == null)
return null;
Node currentNode = node;
Node secondNode = currentNode.getNext();
currentNode.setNext(null);
while (secondNode != null) {
Node temp = secondNode.getNext();
secondNode.setNext(currentNode);
currentNode = secondNode;
secondNode = temp;
}
return currentNode;
}
- 第二种方法
- 第一步，判断节点是否为空，节点是否只有一个
- 第二步，递归遍历，获取到最后一个节点，依次递归回去
- 第三步，将当前节点的下一个节点指向自己，并将当前结点指向为null
- methodTwo 和methodThree相似。
private static Node reverseMethodTwo(Node node) {
// 递归遍历链表。知道找到最后一个节点，并设置其为反转后的新节点，不断递归回传。
if (node == null)
return null;
if (node.getNext() == null)
return node;
Node secondNode = node.getNext();
node.setNext(null);
Node reverseHead = reverseMethodTwo(secondNode);
secondNode.setNext(node);
return reverseHead;
}
private static Node reverseMethodThree(Node node) {
// 递归，区别于方法2
if (node == null)
return null;
if (node.getNext() == null)
return node;
Node reverseNode = reverseMethodThree(node.getNext());
node.getNext().setNext(node);
node.setNext(null);
return reverseNode;
}
完整代码
public class N05 {
/**
* 链表反转
*/
public static void main(String[] args) {
Node node1 = new Node("A");
Node node2 = new Node("B");
Node node3 = new Node("C");
Node node4 = new Node("D");
Node node5 = new Node("E");
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
Node newNode = reverseMethodOne(node1);
print(newNode);
Node node = reverseMethodThree(newNode);
print(node);
}
private static Node reverseMethodOne(Node node) {
// 顺序依次一个一个反转，设置变量temp记录变量
if (node == null)
return null;
Node currentNode = node;
Node secondNode = currentNode.getNext();
currentNode.setNext(null);
while (secondNode != null) {
Node temp = secondNode.getNext();
secondNode.setNext(currentNode);
currentNode = secondNode;
secondNode = temp;
}
return currentNode;
}
private static Node reverseMethodTwo(Node node) {
// 递归遍历链表。知道找到最后一个节点，并设置其为反转后的新节点，不断递归回传。
if (node == null)
return null;
if (node.getNext() == null)
return node;
Node secondNode = node.getNext();
node.setNext(null);
Node reverseHead = reverseMethodTwo(secondNode);
secondNode.setNext(node);
return reverseHead;
}
private static Node reverseMethodThree(Node node) {
// 递归，区别于方法2
if (node == null)
return null;
if (node.getNext() == null)
return node;
Node reverseNode = reverseMethodThree(node.getNext());
node.getNext().setNext(node);
node.setNext(null);
return reverseNode;
}
private static void print(Node newNode) {
while (newNode != null) {
System.out.print(newNode.data + " ");
newNode = newNode.getNext();
}
System.out.println();
}
}
class Node {
String data;
Node next;
public Node(String data) {
super();
this.data = data;
}
public Node(String data, Node next) {
super();
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
参考资料
