单链表的翻转
遍历法
pre：上一个结点 curr：当前结点 temp：临时结点，用于保存当前结点的指针域
基本思路：从前往后修改每个结点的指针。在curr != null的while循环中，先将当前结点curr的下一个结点存到temp即临时结点中，修改当前结点的指针curr.next = pre，然后指针后移，pre = curr curr = temp。最后把原链表的头结点head置为null。返回pre。
public class ListNode {
int val;
ListNode next;
ListNode (int x){ val = x; }
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
ListNode temp = null;
while(curr != null) {
temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
递归翻转
基本思路：在翻转当前结点时，先翻转后续结点。即从尾结点开始，逆向反转各个结点的指针。 把head当作是前一结点，为空链或者当前只有一个结点直接返回head。
private ListNode reverse(ListNode head) {
if(head == null || head.next == null) {return head;}
ListNode reHead = reverse(head.next); //先翻转后续结点
head.next.next = head; //将当前结点的指针域指向前一结点
head.next = null; //前一结点的指针域置为null
return reHead; //返回翻转后新链表的头结点
}
