Reverse Every K Node In List

发表于 | 分类于

Reverse Every K Node In List(将每k个节点逆序)

题目描述：

给定一个链表的头结点head，和一个整数K。将链表中从头到尾链表中的每k个节点逆序，如果最后一段不足k个节点的不进行逆序。

例子：

1->2->3->4->5->6->7->8->NULL.给定的k值为3.则返回的链表排列为:3->2->1->6->5->4->7->8->NULL。

解题思路：

首先涉及到了逆序，第一个想法是利用栈的结构，能够帮助我们将链表中的数据逆序。所以新建一个栈结构和一个计数值，将链表中的值不断压栈，利用计数值来判断是否达到了K个节点。如果达到的话，则从栈中不断出栈数据，然后修改链表中的数据即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "ListNode.h"
#include <stack>
using namespace std;
class reverseKNodes1{
public:
    ListNode* reverseKNodes(ListNode*head, int K){
        if (K < 2)
            return head; // 逆序K小于2的情况直接返回
        stack<int> stk;
        int count = 0;
        ListNode* cur = head;//用来记录当前的遍历节点
        ListNode* tmp = head;//用来保存每k个节点的头节点
        while(cur != NULL){
            if (count != K){
                stk.push(cur->val);
                count = count + 1;
                cur = cur->next;
            }// 将数据进栈，直到栈中k个数
            else{
                while(!stk.empty()){
                    tmp->val = stk.top();
                    stk.pop();
                    tmp = tmp->next;
                }//根据出栈的数修改链表中的数据
                tmp = cur;// 重新修改当前每k个小链表的头节点
                count = 0;
            }
        }
        return head;
    }
};

解题思路2：

当然我们也可以不用栈结构直接进行链表的调整。主要的思路是用start记录每k个节点的头，end用来记录k个节点的尾。然后直接将k个节点进行逆序。主要需要注意的地方有：第一组k个节点的尾部成为返回的头节点，需要记录；另外后面的每组k个节点，我们都需要将逆序后的k个节点的头部与上一组的k个节点的尾部重新连接。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class reverseKNodes2{
public:
    ListNode* reverseKNodes(ListNode* head, int K){
        if (K < 2)
            return head;
        ListNode* cur = head; //遍历节点
        ListNode* start = NULL;
        ListNode* pre = NULL; // 上一组k个节点的尾部
        ListNode* next = NULL; //下一组k个节点的头部
        int count = 1;
        while(cur != NULL){
            next = cur->next;
            if (count == K){
                start = pre == NULL ? head : pre->next;
                head = pre == NULL ? cur : head;// 记录返回的头结点
                resign(pre, start, cur, next);// 逆序函数
                pre = start;// 修改pre节点
                count = 0;
            }
            count++;
            cur = next;
        }
        return head;
    }
    void resign(ListNode* left, ListNode* start, ListNode* end, ListNode* right){
        ListNode* pre = start;
        ListNode* cur = start->next;
        ListNode* next = NULL;
        while (cur != right){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        if (left != NULL){
            left->next = end;
        }
        start->next = cur;
    }
};