题意：给定链表表头，反转链表，返回反转链表的表头
【循环】题解：
head维护原链表当前节点，nHead维护反转链表的头节点，nHead置于head前一位，依次后移，直至head到链表尾结束。
双指针循环版本
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
ListNode nHead = new ListNode(head.val, null);
while(head.next != null) {
head = head.next;
nHead = new ListNode(head.val, nHead);
}
return nHead;
}
}
【双指针递归】题解：
一句话总结：每次递归都返回原链表[表头至当前节点]子链表的反转链表的表头！
定义递归函数ListNode reverse(ListNode head, ListNode lastNewHead)，
- head：表示原链表的当前节点
- lastNewHead：表示反转链表的当前节点
在原链表中，lastNewHead位于head之前，如下图：
每次迭代更新反转链表的头节点nHead = ListNode(head.val, lastNewHead)
递归：往后移动head和lastNewHead
递归结束标志：遍历到原链表链尾，此时返回反转链表的头节点
双指针递归版本
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
return reverse(head, null);
}
public ListNode reverse(ListNode head, ListNode lastNewHead) {
ListNode nHead = new ListNode(head.val, lastNewHead);
if(head.next == null) return nHead;
return reverse(head.next, nHead);
}
}
【递归妙解】题解2：
一句话总结：每次递归返回原链表[当前节点至链表尾]的局部反转链表的表头！
如下图，原链表的4、5节点已经被反转完成，当前节点为head=3，继续添加3节点至反转链表中，就是使反转链表表头head.next=4的next节点为head=3即可，也就是head.next.next = head，注意：必须保证原链表表头在反转链表中的next为null！
妙解！！
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode res = reverseList(head.next);
head.next.next = head;
head.next = null;
return res;
}
}