反转链表【递归】

今天复习递归的时候遇见了一个大家都觉得很简单的题：反转链表

把自己别住了 想明白了觉得说这题用了这么久真的好丢人。。。。。。

详细的写下来，如果下次遇见再不会 我就打死我自己。。。。

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 先把节点写出来

public class Node {
      int val;
      Node next;
      Node() {}
      Node(int val) { this.val = val; }
      Node(int val, ListNode next) { this.val = val; this.next = next; }
  }

方法一：将头结点指向null； 变成最后一个结点；提前把第2保存在temp中。第二个结点指向第一个结点.....结束条件是cur=null

代码实现：  

    public Node reverseList(Node head) {
        Node temp;
        Node cur;
        Node pre;
        pre = null;
        cur = head;

        while
        (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;

        }
        return pre;
    }

 

 

方法二：递归

找到结束递归的方法：当head或者head.next=null时，它的反转链表就是head  

用链表1，2，3，4举例：

public static Node reverseList2(Node head) {
        // 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }
//第一次递归结束，返回的head=4；

        Node newList = reverseList2(head.next);//反转链表
         //返回上层递归 当head.next=3，传入reverseList2时head=3；
        head.next.next = head;
         //此时 head.next.next是4的下一个结点，那么把现在的head=3给head.next.next 即 
        （head.next.next = head） 
        //也就是说明4的下一个结点是3  
        head.next = null;

        //将3的下一个结点指向null  即将原来的3与4之间的连接断开
        return newList;
    }

画图理解更清晰

over