数据结构-单链表反转

单链表是一种线性数据结构，由当前节点数据和指向下个节点的指针组成，因为是单向的，所以称为单链表

单链表的反转：

例如：1—>2—>3—>4 反转成：4—>3—>2—>1

首先定义一个链表的节点：

public class Node {
 private int data;
 private Node next;

 public Node(int data) {
 this.data = data;
 next = null;
 }
 //添加节点
 public Node addNode(Node node) {
 next = node;
 return node;
 }

 public void setNext(Node next) {
 this.next = next;
 }

 public Node getNext() {
 return next;
 }

 @Override
 public String toString() {
 return "Node{" +
 "data=" + data +
 ", next=" + next +
 '}';
 }
}

方式一：遍历节点，反转每个节点，也叫头插法，因为节点依次插入了新链表的头部

因为单链表只有指向下一个节点的指针，没有指向上个节点的指针。所以我们可以定义个指针指向上个节点，这样我们遍历链表，把每个指向下个节点的指针，指向上个节点，这样每个节点都指向了上个节点，实现了反转。如下图所示：

preNode 指向上个节点，curNode指向当前节点，让curNode的next指向preNode,然后移动preNode 和 curNode ，这样最终以preNode为头结点，实现了单链表的反转

代码：

public Node reverse() {
if (this == null || this.next == null) {
return this;
}
//上个节点
Node preNode = null;
//当前节点
Node curNode = this;
while (curNode != null) {
//当前节点的下个节点
Node next = curNode.getNext();
//修改当前节点的下个节点，让其指向上个节点
curNode.setNext(preNode);
//上个节点移动到当前节点
preNode = curNode;
//当前节点移动到下个节点
curNode = next;
}
return preNode;
}

测试：

public class Test {
 public static void main(String[] args) {
 Node head = new Node(1);
 head.addNode(new Node(2)).addNode(new Node(3));
 System.out.println("反转前：" + head);
 Node reverse = head.reverse();
 System.out.println("反转后：" + reverse);
 }
}
结果：
反转前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反转后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}

方式二：借助栈的特性，先进后出，实现单链表的反转

public static Node reverse2(Node head) {
 if (head == null || head.next == null) {
 return head;
 }
 Stack<Node> stack = new Stack<>();
 while (head != null) {
 stack.push(head);
 head = head.getNext();
 }
 head = stack.pop();
 //当前节点的位置
 Node cur = head;
 while (!stack.isEmpty()) {
 Node node = stack.pop();
 node.next = null;
 cur.next = node;
 cur = node;
 }
 return head;
}

方式三：递归

递归的方式理解起来，感觉有点困难

public static Node reverse3(Node head) {
 if (head == null || head.next == null) {
 return head;
 }
 Node prev = reverse3(head.next);
 head.next.next = head;
 head.next = null;
 return prev;
}

测试

public class Test {
 public static void main(String[] args) {
 Node head = new Node(1);
 head.addNode(new Node(2)).addNode(new Node(3));
 System.out.println("反转前：" + head);
 Node reverse = Node.reverse3(head);
 System.out.println("反转后：" + reverse);
 }
}
结果：
反转前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反转后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}