剑指Offer刷题记录，第七题。

方法一：迭代法

思路：迭代法需要三个指针，分别是pre、cur以及nxt，用于顺序遍历链表。初始化时，pre指向空节点(头结点的next指向)，cur指向头结点head，nxt指向head.next，同时由于head.next可能不存在，所以放在循环体中去初始化。迭代过程如下:
(1) nxt指向cur.next
(2) cur.next指向pre
(3) pre移动到cur位置
(4) cur移动到nxt位置
退出时，返回pre；

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
import java.util.*;
public class Solution {
   
    public ListNode ReverseList(ListNode head) {
   
        if (head == null || head.next == null) {
   
            return head;
        }
        ListNode pre = null, cur = head;
        while (cur != null) {
   
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre; 
    }
}

时间复杂度： O(N), 因为需要正向遍历一遍链表。
空间复杂度： O(1), 未使用额外存储空间。

方法二：递归法

思路：该问题是满足递归 条件的，即大问题可以划分为子问题、子问题求解方式和大问题一样、存在最小子问题。具体到这道题即为：链表的反转可以化为头结点与头结点之后的节点反转两个子问题，而之后的节点反转又可以再次划分，到最后只剩下一个节点，或者该节点不存在即达到递归终止条件。而到每一层回归时，我们只需将当前head赋给head.next.next,而将null赋给head.next即可。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
import java.util.*;
public class Solution {
   
    public ListNode ReverseList(ListNode head) {
   
    	// 递归终止条件
        if (head == null || head.next == null) {
   
            return head;
        }
        ListNode newHead = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead; 
    }
}

时间复杂度： O(N), 因为需要正向遍历一遍链表。
空间复杂度： O(N), 需要额外使用一个Stack来存放链表元素。
总结：本题考频极高，迭代写法类似于双指针，递归写法略微抽象。但这两种写法必须写得滚瓜烂熟！画图理解链表问题是最直观的方法 ！