【leetcode每日一题】25.Reverse Nodes in k-Group

拼搏现实的明天。 2022-08-04 13:59 3阅读 0赞

题目：

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）判断链表的节点数与给定k值的关系，如果节点数小于k值，则不用逆序操作，直接返回；如果节点数大于等于k值，则继续进行下面操作。

2）找到逆序后新链表的头结点，即原链表的第k个节点。

3）将链表节点以k个为单位依次压入栈中，判断压入节点的个数与k值的关系。如果压入节点个数等于k值，则将k个节点依次出栈，进行逆序操作；如果压入节点个数小于k值，则直接返回原来链表的顺序。

代码如下：

/**
     * 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(head==NULL||head->next==NULL)
                return head;
            int num=0;
            ListNode *temp=head,*p=head,*q=head;
            ListNode *result,*tail;
            stack <ListNode*> nodes;
            while(temp!=NULL)
            {
                num++;
                temp=temp->next;
            }
            if(num<k)   //判断链表长度是否小于给定的k值，如果小，则直接返回。
                return head;
            temp=head;
            for(int i=0;i<k-1;i++)
                temp=temp->next;    //找到逆序后的头节点
            result=temp;
            while(p!=NULL)
            {
                int i;
    			tail=p;         //剩余链表部分的头结点
                for(i=0;i<k;i++)
                {
                   if(p!=NULL)
                   {
                       nodes.push(p);
                       p=p->next;
                   }
                   else
                       break;
                }
                if(i==k)        //如果剩余节点数大于等于K个
                {
                    while(!nodes.empty())
                    {
                        temp=nodes.top();   //链表逆序操作
                        q->next=temp;
                        q=q->next;
                        nodes.pop();
                    }
                    q->next=NULL;
                }
                else
                    q->next=tail;   //如果剩余节点数小于k个，则后链表不进行逆序操作
            }
            return result;
        }
    };