java_链表反转

qq448852160 2018-12-04 原文

定义一个Node节点类

 1 1 public class Node {
 2  2     public int value;
 3  3     public Node next;
 4  4 
 5  5     public Node(int value) {
 6  6         this.value = value;
 7  7     }
 8  8 
 9  9     @Override
10 10     public String toString() {//重写toString方法，方便打印节点
11 11         return value+"";
12 12     }
13 13 }

View Code

循环迭代

 1 1 public static Node reverseList1(Node head){
 2  2         Node pre = null;
 3  3         Node next = null;
 4  4         while(head!=null){
 5  5             next = head.next;//记录当前节点的下一个节点，防止断链
 6  6             head.next = pre;//指针反转
 7  7             //光标移向下一个节点
 8  8             pre = head;
 9  9             head = next;
10 10         }
11 11         return pre;
12 12     }

假设创建如下4个节点，并调用reverseList1

 1  1 public static void main(String[] args){
 2  2         Node n1 = new Node(1);
 3  3         Node n2 = new Node(2);
 4  4         Node n3 = new Node(3);
 5  5         Node n4 = new Node(4);
 6  6         n1.next = n2;
 7  7         n2.next = n3;
 8  8         n3.next = n4;
 9  9         System.out.println(reverseList1(n1));
10 10     }

View Code

之后重复循环直至head==null退出循环

程序执行结果如下

递归

递归的思想是head.next.next=head,以此类推；
实现的关键是找到临界点（递推头：何时退出递归），当head.next==null时，说明已经递归到最后一个节点了，此时不再递归调用

 1  1 public static Node reverseList2(Node head){
 2  2         if(head==null||head.next==null){//递归头
 3  3             return head;
 4  4         }else{
 5  5             Node reversed = reverseList2(head.next);//调用自身方法
 6  6             //递归体
 7  7             head.next.next = head;
 8  8             head.next = null;
 9  9             return reversed;
10 10         }
11 11     }

假设创建如下4个节点，并调用reverseList2

 1 public static void main(String[] args){
 2         Node n1 = new Node(1);
 3         Node n2 = new Node(2);
 4         Node n3 = new Node(3);
 5         Node n4 = new Node(4);
 6         n1.next = n2;
 7         n2.next = n3;
 8         n3.next = n4;
 9         System.out.println(reverseList1(n1));
10     }