反转链表

n个月前我玩过一次反转链表，大概有两种方法，一种是while循环遍历，另外一种是递归，今天带大家理解一下递归的实现逻辑
递归实现反转链表，其实就是系统帮我们压栈的过程每递归一次，指向不同的下一个节点

大致的流程就是上图所示 ， 下面来理解上图这个逻辑
话不多说上代码

class ListNode {int val;ListNode next;ListNode(int x) {val = x;}@Overridepublic String toString() {return this.val + " - > " + this.next;}
}
public class LinkedList {public static void main(String[] args) {ListNode listNode = new ListNode(1);listNode.next = new ListNode(2);listNode.next.next = new ListNode(3);listNode.next.next.next = new ListNode(4);System.out.println(listNode);ListNode listNode1 = reverse(listNode);System.out.println(listNode1);}public static ListNode reverse(ListNode head) {if (head == null || head.next == null) {System.out.println(head.hashCode());return head;}ListNode temp = head.next;ListNode newHead = reverse(head.next);System.out.println("head ===>   " + head);System.out.println("temp ===>   " + temp);System.out.println("new head before  ============>  " + newHead);temp.next = head;head.next = null;System.out.println("new head after   ============>  " + newHead);return newHead;}
}

下面是控制台的输出

1 - > 2 - > 3 - > 4 - > null
head ===>   3 - > 4 - > null
temp ===>   4 - > null
new head before  ============>  4 - > null
new head after   ============>  4 - > 3 - > null
head ===>   2 - > 3 - > null
temp ===>   3 - > null
new head before  ============>  4 - > 3 - > null
new head after   ============>  4 - > 3 - > 2 - > null
head ===>   1 - > 2 - > null
temp ===>   2 - > null
new head before  ============>  4 - > 3 - > 2 - > null
new head after   ============>  4 - > 3 - > 2 - > 1 - > null
4 - > 3 - > 2 - > 1 - > null

• 我们很容易的发现返回的newHead 贯穿了整个递归，方法最后返回的也是newHead这个对象，但这时候可能有人就要问了，我并没有对newHead 这个对象进行改变啊，怎么就能反转链表了呢，其实虽然我们没有对这个对象进行操作，但我们维护的是对象引用，这个引用在其他地方做了操作，自然就可以变化
• 我们可以在 new head before 和 new head after 这两个输出中看出，new head after 就是每递归一次得出的对象
  接下来就是弄清楚这代码中间到底做了什么操作了，才使得new head after 是正确的结果

在代码中 temp=head.next 并且
看到控制台的输出不难发现，递归的层级关系，下层只是上层的 next 而已
他们俩相差的值正是我需要的，这时候只要把   temp.next = head 的指向变一下
就是最后的值在前面，之前的值在后面，他们的位置交换一下，
再把 head.next = null; 指向为null，不然就嵌套引用了，以此类推，没当一次递归结束后，
就会把前一个值变成后一个的子节点，这就完成了反转链表的操作
是不是so easy呢？？

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！