本文共 2806 字，大约阅读时间需要 9 分钟。

题目：

给定一个单链表的头结点head，实现一个调整单链表的函数，使得每k个节点之间逆序，如果最后不管k个节点一组，则不调整最后几个节点。

Example：

链表：1->2->3->4->5->6->7->8->nullptr, k = 3

调整后：3->2->1->6->5->4->7->8->nullptr

代码1：

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x),next(nullptr){}};ListNode* resign(stack
      
        &s, ListNode* left, ListNode* right){    ListNode* cur = s.top(); s.pop();    left->next = cur;    while (!s.empty())    {        ListNode* next = s.top(); s.pop();        cur->next = next;        cur = next;    }    cur->next = right;    return cur;}ListNode* reverseKNode(ListNode *head, int k){    if (head == nullptr || head->next == nullptr || k < 2)        return head;    ListNode* newHead = new ListNode(-1);    newHead->next = head;    ListNode* pre = newHead;    ListNode* cur = head;    stack
       
         s;    while (cur != nullptr)    {        ListNode* next = cur->next;        s.push(cur);        if (s.size() == k)        {            pre = resign(s, pre, next);        }        cur = next;    }    return newHead->next;}int main(){    ListNode *head = new ListNode(1);    ListNode* node1 = new ListNode(2);    ListNode* node2 = new ListNode(3);    ListNode* node3 = new ListNode(4);    ListNode* node4 = new ListNode(5);    ListNode* node5 = new ListNode(6);    ListNode* node6 = new ListNode(7);    ListNode* node7 = new ListNode(8);    head->next = node1;    node1->next = node2;    node2->next = node3;    node3->next = node4;    node4->next = node5;    node5->next = node6;    node6->next = node7;    head = reverseKNode(head, 3);    while (head != nullptr)    {        cout << head->val << " ";        head = head->next;    }    return 0;}
       
      
     
    
   

代码2：

struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(nullptr) {}};void resign(ListNode* left, ListNode* start, ListNode* end, ListNode* right){    ListNode* pre = start;    ListNode* cur = start->next;    ListNode* next = nullptr;    while (cur != right)    {        next = cur->next;        cur->next = pre;        pre = cur;        cur = next;    }    left->next = end;    start->next = right;}ListNode* reverseKNode(ListNode* head, int k){    if (head == nullptr || head->next == nullptr || k < 2)        return head;    ListNode* newHead = new ListNode(-1);    newHead->next = head;    ListNode* pre = newHead;    ListNode* start = head;    ListNode* cur = head;    ListNode* next = nullptr;    int count = 1;    while (cur != nullptr)    {        next = cur->next;        if (count == k)        {            start = pre->next;            resign(pre, start, cur, next);            pre = start;            count = 0;        }        ++count;        cur = next;    }    return newHead->next;

参考资料：

左程云著《程序员代码面试指南》

转载地址：http://gvwab.baihongyu.com/