模块化思想（基于LeetCode-25）

总结

许多问题都可以分解为不同的子问题，将子问题写成单独的函数，可以使得整个程序结构更加清楚；

在归并排序中，将归并的步骤单独列出；在快速排序中，将分割的步骤单独列出；在翻转列表的问题中，将翻转的方式单独列出。

题目：K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

代码实现

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int x): int val, next(NULL){}
};
class solution{
public:
  pair<ListNode*, ListNode*> reverse(ListNode* head, ListNode* tail){
    ListNode* prev = tail->next;//作为指针指向的位置
    ListNode* p = head;//当前用于处理的节点
    while(prev != tail){
      ListNode* nex = p->next;
      p->next = prev;
      prev = p;
      p = nex;
    }
    return{tail, head};
  }
  ListNode* reverseKGroup(ListNode* head, int k){
    //在reverse函数中，假定了用于排序的链表前后都有元素，故直接在链表前方添加一个节点
    ListNode* newhead = new ListNode(0);
    newhead->next = head;
    //使用prev表示在进行此次翻转前的位置，prev->next指向翻转后的起点
    ListNode* prev = newhead;
    while(head){
      //从prev开始往后遍历k次，确定遍历终点
      ListNode* tail = prev;
      for (int i = 1; i <= k; ++i){
        tail = tail->next;
      }
      //保留当前的后一个节点，翻转后的最后一个节点指向此处
      ListNode* nex = tail->next;
      tie{head, tail} = reverse(head, tail);
      //插入片段
      prev->next = head;
      tail->next = nex;
      //更新prev和头部
      prev = tail;
      head = tail->next;
    }
  }
  return newhead;
}

模块化思想

模块化思想（基于LeetCode-25）

总结

题目：K 个一组翻转链表

代码实现

FEATURED TAGS

FRIENDS