1. Reverse Linked List
题目要求：
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
初想用递归来实现应该会挺好的，但最终运行时间有点久，达到72ms，虽然没超时。具体程序如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* recurList(ListNode* p)
{
if (p->next != NULL)
{
ListNode* tmp = p->next;
if (tmp->next == NULL)
{
tmp->next = p;
p->next = NULL;
return tmp;
}
} ListNode* ret = recurList(p->next);
ListNode* tmp = ret;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = p;
p->next = NULL;
return ret;
} ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL)
return head; ListNode* tail = recurList(head);
return tail;
}
在LeetCode论坛发现了一个8ms的解法，不得不为其简洁高效合彩！具体程序如下：
ListNode* reverseList(ListNode* head) {
ListNode *curr = head, *prev = nullptr;
while (curr) {
auto next = curr->next;
curr->next = prev;
prev = curr, curr = next;
}
return prev;
}
2. Reverse Linked List II
题目要求：
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
该题的解法可以将一个链表分成三个部分，即1~m-1、m~n、n+1~最后一个元素3个部分，且仅对中间部分进行翻转，最后再将这3个部分合并。具体程序如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(!head || !head->next || m >= n)
return head; ListNode *start = head;
ListNode *preList = nullptr, *postList = nullptr; int k = ;
while(k < m)
{
preList = start;
start = start->next;
k++;
} ListNode *prev = nullptr;
while(k <= n)
{
if(k == n)
postList = start->next;
auto next = start->next;
start->next = prev;
prev = start;
start = next;
k++;
} ListNode *end = prev;
while(end && end->next)
end = end->next; if(preList)
preList->next = prev;
else
head = prev;
end->next = postList; return head;
}
};