剑指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来存放链表元素。
总结：本题考频极高，迭代写法类似于双指针，递归写法略微抽象。但这两种写法必须写得滚瓜烂熟！画图理解链表问题是最直观的方法 ！
