[LeetCode] Reverse Linked List II

解题思路与上一篇Reverse Linked List类似，只不过这里是反转部分链表。
因此，只需将m到n部分翻转，然后将m的前缀beforeM指向该部分反转后的头结点即可。如果beforeM为NULL，则m=1，m到n部分的头结点即为链表的头结点。

//Runtime: 4 ms

#include iostream 

#include cstdlib 

#include cmath 

using namespace std;

struct ListNode{

 int val;

 ListNode *next;

 ListNode(int x) : val(x), next(NULL) {}

class Solution {

public:

 ListNode* reverseBetween(ListNode* head, int m, int n) {

 ListNode *cur = head;

 ListNode *beforeM = NULL;

 for (int i = 1; i m; i++)

 beforeM = cur;

 cur = cur- next;

 ListNode *localhead = cur;

 ListNode *pre = cur;

 cur = cur- next;

 int count = n - m;

 while (count--)

 pre- next = cur- next;

 cur- next = localhead;

 localhead = cur;

 cur = pre- next;

 if (beforeM == NULL)

 head = localhead;

 else

 beforeM- next = localhead;

 return head;

void printList(ListNode *head)

 while(head != NULL)

 cout head- val " ";

 head = head- next;

 cout endl;

void dropList(ListNode *head)

 if (head == NULL) return;

 ListNode *temp;

 while (head != NULL)

 temp = head- next;

 delete head;

 head = temp;

int main()

 ListNode *head = new ListNode(0);

 ListNode *cur = head;

 for (int i = 0; i 10; i++)

 ListNode *newnode = new ListNode(floor(rand()%77));

 cur- next = newnode;

 cur = newnode;

 printList(head);

 Solution s;

 head = s.reverseBetween(head, 2, 5);

 printList(head);

 dropList(head);

LeetCode 328. Odd Even Linked List 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
LeetCode 142. Linked List Cycle II 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
LeetCode 234：回文链表 Palindrome Linked List ​请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1- 2 输出: false 示例 2: 输入: 1- 2- 2- 1 输出: true 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ Follow up:Could you do it in O(n) time and O(1) space? 解题思路： 首先是寻找链表中间节点，这个可以用快慢指针来解决，快指针速度为2，慢指针速度为1，快指针遍历完链表时，慢指针刚好走到中间节点（相对）。
LeetCode 328：奇偶链表 Odd Even Linked List ​给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。