220415链表反转

方法一：迭代法

public class ReverseList {
    static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
   public static ListNode iterate(ListNode head) {
        ListNode pre = null,next;
        ListNode curr = head;
        while (curr != null) {
            // 保存当前节点的下一个节点信息
            next = curr.next;
            // 当前节点指向上一个节点
            curr.next = pre;
            // 为了循环
            // 当前节点赋值为上一个节点
            pre = curr;
            // 下一个节点赋值为当前节点
            curr = next;
        }
        return pre;
    }
   public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        ListNode prev = iterate(node1);
        System.out.println(prev);
    }
}

方法二：递归法

public static ListNode recursion(ListNode head) {
        // 递归找到倒数第二个节点
        if (null == head || null == head.next) {
            return head;
        }
        // 这里最终返回的是最后一个节点
        ListNode new_head = recursion(head.next);
        head.next.next = head;
        head.next = null;
        // 将递归最终返回的最后一个节点一直往上传，反转后最后一个节点又是第一个节点
        return new_head;
    }

// 可以先理解下面这个递归方法，这种方式在平常可能会更常见
// 这个方法解决了链表的反转，但是没有返回值，我们查不到这个链表了
// 然后再看上面解决我们链表反转的递归方法，把递归方法最终返回的尾节点一直往上传递，
// 又因为反转后尾节点会变成头结点，所以这个就会是我们的结果
 public static void recursion(ListNode head) {
        // 递归找到倒数第二个节点
        if (null == head || null == head.next) {
            return head;
        }
        recursion(head.next);
        head.next.next = head;
        head.next = null;
    }