题目：
leetcode 206.Reverse Linked List(easy)
Reverse a singly linked list.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
题目大意：
将一个单链表如上图所示翻转输出。
解题思路：
有两种思路：一种是头插法的迭代的方法(iteratively),还有一种递归的方法(recursively)。
第一种思路比较简单，但是需要记住代码中有两个指针pre和cur需要维护，还有循环体内的指针next和语句执行顺序(4条)；
第二种思路将问题划分为 规模更小的 同质的 basecase，这里将问题依次划分为2->3->4->5->NULL、3->4->5->NULL、4->5->NULL、5->null。最内层中，head为4(只有第一次newhead是5，是head.next)，head.next为5，调整指针满足局部要求，然后依次从后往前处理，每次处理新加情况。处理完应该是null->5->4->3->2->1->null,但是只返回5->4->3->2->1->null;
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34Java:
iteratively:
public ListNode reverseList(ListNode head){
if(head == null) return head;
ListNode pre = null, cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
recursively:
public ListNode reverseList(ListNode head){
if(head == null || head.next == null) return head;
/*
这个base case写成这样并不多余。
head == null 判断特殊样例，如空链表的情况
head.next == null 则是递归的出口case，这样写保证之后的代码不会出现空指针异常
*/
ListNode newHead = reverseList(head.next);
head.next.next = head;
/* 这里不能写成newHead.next = head;
因为从始至终newHead都没有变化，一直都是最后一个非空结点，变化的只是head,
只有最内层时head.next和newHead指的是同一个结点. */
head.next = null;
return newHead;
}
Python:
