Reverse Nodes in k-Group--LeetCode

水深无声 2022-08-07 10:46 18阅读 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`

`思路：先反转链表，然后再连接`

#include <iostream>
    #include <vector>
    using namespace std;
    /*
    按照规定 做K反转 
    */
    typedef struct list_node List;
    struct list_node
    {
    	int value;
    	struct list_node* next;
    };
    
    void Init_List(List*& head,int* array,int n)  
    {  
        head = NULL;  
        List* tmp;  
        List* record;  
        for(int i=1;i<=n;i++)  
        {  
            tmp = new List;  
            tmp->next = NULL;  
            tmp->value = array[i-1];  
            if(head == NULL)  
            {  
                head = tmp;  
                record = head;  
            }  
            else  
            {  
                record->next = tmp;  
                record = tmp;  
            }  
        }  
    }  
    void print_list(List* list)  
    {  
        List* tmp=list;  
        while(tmp != NULL)  
        {  
            cout<<tmp->value<<endl;  
            tmp = tmp->next;   
        }  
    }  
    
    
    /*反转链表List 是的新的头部为head 新的尾部为tail*/
    void Reverse_list(List*& list,List*& head,List*& tail)
    {
    	if(list == NULL || list->next == NULL)
    		return ;
    	head = list;
    	tail = list;
    	List* cur=NULL;
    	List* next;
    	while(head !=NULL)
    	{
    		next = head->next;
    		head->next=cur ;
    		cur = head;
    		head = next;
    	}
    	list =cur;
    	head = cur;
    }
    
    /*做K个节点的反转*/
    void Reverse_k(List*& list,int k)
    {
    	int num = 1;
    	int flag =1;
    	if(list == NULL || list->next == NULL || k<=0)
    		return;
    	List* head,*tail,*next,*pre;
    	head = list;
    	tail = list;
    	while(tail != NULL && tail->next != NULL)
    	{
    		tail = tail->next;
    		num++;
    		if(num == k)
    		{
    			if(tail != NULL)
    			{
    				next = tail->next;
    				tail->next = NULL;		
    			}		
    			else
    				next = NULL;
    			print_list(head);
    			cout<<"============"<<endl;
    			Reverse_list(head,head,tail);
    			
    			if(flag)
    			{
    				list = head;
    				flag =0;
    				pre = tail;
    			}
    			else //第二次以后的反转 
    			{
    				pre->next = head;
    				pre = tail; 
    			}
    			//tail->next = next;
    			head = next;
    			tail = next;
    			num =1;
    		}
    	}
    	pre->next = head;
    }
       
    int main() 
    {
    	int array[]={1,2,3,4,5,6,7,8,9,10,11,12};
    	List* list,*head,*tail;
    	Init_List(list,array,sizeof(array)/sizeof(int));
    	Reverse_k(list,3);	
    	print_list(list); 
    	return 0;
    }

思路：上述代码不是特别规范，其实可以使用简单的思维来构造，每次都是记录需要转换的这段链表，只不过需要记录需要转换的前一个节点到最后一个需要转换的节点。

void Reverse(List*& head,List*& tail)
    {
    	List* cur=NULL,*temp,*pre=tail->next;
    	temp= head->next;
    	while(cur != tail)
    	{
    		cur = temp;
    		temp = temp->next;
    		cur->next = pre;
    		pre = cur;
    	}
    	tail = head->next;
    	head->next = cur;
    } 
    List* Reverse_K(List* head,int k)
    {
    	List* newhead = new List;
    	newhead->next = head;
    	List* slow=newhead;
    	List* fast=newhead->next;
    	int count;
    	while(fast != NULL)
    	{
    		count = 1;
    		while(fast !=NULL && count <k)
    		{
    			fast = fast->next;
    			count++;
    		}
    		if(count<k)
    			break;
    		else
    		{
    			Reverse(slow,fast);	
    			slow = fast;
    			fast = fast->next;
    		}
    	}
    	return newhead->next;
    }