LeetCode-025-Reverse Nodes in k-Group

Problem

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Examples:

Input: 1-2-3-4-5
Output:

k=2, 2-1-4-3-5
k=3, 3-2-1-4-5
{% endnote %}

Solutions

递归, 每次改变k个节点的链接顺序, 然后令最后一个节点的next等于下一次递归的返回值, 最后返回头节点, 如果本次不满k个, 直接返回. 每次递归的内容可以是迭代或者用栈, 两种方式的时间差不多
迭代, 基于第24题的迭代, 每次修改完一段之后, 要将此段和前一段相连, 还要和后一段相连, 要注意很多细节
利用栈, 因为k个节点进栈顺序和出栈顺序正好相反

C++ Codes

节点数据结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

递归+栈

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1 || head==NULL) return head;
        ListNode* stack[k];
        ListNode *p=head;
        //存入栈中
        for(int i=0;i<k;i++){
            if(p==NULL)return head;
            stack[i]=p;
            p=p->next;
        }
        //逆序
        for(int i=k-1;i>0;i--){
            stack[i]->next=stack[i-1];
        }
        //和后一段相连
        stack[0]->next=reverseKGroup(p, k);
        //每次递归返回头节点
        return stack[k-1]; 
    }
};

纯迭代, 相对递归感觉比较麻烦, 逻辑上要想更多, 但是资源肯定比递归消耗少

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1) return head;
        ListNode *front, *rear, *tmp, *p, *q, *s;
        front=head;
        for(int i=0;i<k;i++){
            if(front!=NULL) front=front->next;
            else return head;
        }
        front=rear=head;
        //front指向第一个节点, rear指向k+1个节点
        for(int i=0;i<k;i++){
            if(i==k-1) head=rear;
            rear=rear->next;
        }
        
        //pre是前一段最后一个节点
        ListNode *pre=new ListNode(0);
        while(true){
            p=front;q=front->next;s=q->next;
            while(q!=rear){
                q->next=p;
                p=q;q=s;
                //这里要注意rear可能是NULL, s->next需判断
                if(s==rear && s==NULL) break;
                else s=s->next;                
            }
            //本段和后一段相连,此时q=rear, s=rear->next, 
            front->next=rear;
            //前面一段和本段第一个节点相连 
            pre->next=p;
            pre=front;
            //更新front和rear
            front=rear;
            for(int i=0;i<k;i++) {
                //rear可能没到目标就成了NULL
                if(rear==NULL)return head;
                rear=rear->next;
            }
        }
        return head;  
    }
};

Python Codes