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.

这题要求我们翻转[m, n]区间之间的链表。对于链表翻转来说，几乎都是通用的做法，譬如p1 -> p2 -> p3 -> p4，如果我们要翻转p2和p3，其实就是将p3挂载到p1的后面，所以我们需要知道p2的前驱节点p1。伪代码如下：

  1.     //保存p3
  2.     n = p2->next;
  3.     //将p3的next挂载到p2后面
  4.     p2->next = p3->next;
  5.     //将p3挂载到p1的后面
  6.     p1->next = p3;
  7.     //将p2挂载到p3得后面
  8.     p3->next = p2;

对于上题，我们首先遍历得到第m - 1个node，也就是pm的前驱节点。然后依次遍历，处理挂载问题就可以了。

代码如下：

  1. class Solution {
  2. public:
  3.     ListNode *reverseBetween(ListNode *head, int m, int n) {
  4.         if(!head) {
  5.             return head;
  6.         }
  8.         ListNode dummy(0);
  9.         dummy.next = head;
  11.         ListNode* p = &dummy;
  12.         for(int i = 1; i < m; i++) {
  13.             p = p->next;
  14.         }
  16.         //p此时就是pm的前驱节点
  17.         ListNode* pm = p->next;
  19.         for(int i = m; i < n; i++) {
  20.             ListNode* n = pm->next;
  21.             pm->next = n->next;
  22.             n->next = p->next;
  23.             p->next = n;
  24.         }
  26.         return dummy.next;
  27.     }
  28. };

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

这题要求我们按照每k个节点对其进行翻转，理解了链表如何翻转之后很容易处理，唯一需要注意的就是每次k个翻转之后，一定要知道最后一个节点，因为这个节点就是下组的前驱节点了。

  1. ListNode *reverseKGroup(ListNode *head, int k) {
  2.         if(k <= 1 || !head) {
  3.             return head;
  4.         }
  6.         ListNode dummy(0);
  7.         dummy.next = head;
  8.         ListNode* p = &dummy;
  9.         ListNode* prev = &dummy;
  11.         while(p) {
  12.             prev = p;
  13.             for(int i = 0; i < k; i++){
  14.                 p = p->next;
  15.                 if(!p) {
  16.                     //到这里已经不够k个没法翻转了
  17.                     return dummy.next;
  18.                 }
  19.             }
  21.             p = reverse(prev, p->next);
  22.         }
  24.         return dummy.next;
  25.     }
  27.     ListNode* reverse(ListNode* prev, ListNode* end) {
  28.         ListNode* p = prev->next;
  30.         while(p->next != end) {
  31.             ListNode* n = p->next;
  32.             p->next = n->next;
  33.             n->next = prev->next;
  34.             prev->next = n;
  35.         }
  37.         //这里我们会返回最后一个节点，作为下一组的前驱节点
  38.         return p;
  39.     }