反转链表 - 简书

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/

解法1：

使用while循环依次变更指针

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode now = null;
         ListNode temp = null;
        while(head != null) {
            temp = head.next;
            head.next = now;
            now = head;
            head = temp;
         }
        return now;
    }
}

时间复杂度 O(n)
now 存储当前节点head，temp存储下一节点next，每次while循环会将head.next指向上一次循环时留下的now，而temp再次更改为当前节点的next

解法2：

使用递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode now = reverseList(head.next);
        head.next.next = head;
         head.next = null;
         return now;
    }
}

时间复杂度O(n)
本质是递归到最后一个节点，然后从最后一个节点向前反转指针，和解法1本质上类似，只是顺序从后往前，
head.next = null;用来防止死循环内存溢出，now始终为5，不参与反转