Reverse Linked List II--LeetCode

野性酷女 2022-08-07 11:51 27阅读 0赞

# 题目： #

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:  
Given `1->2->3->4->5->NULL`, m = 2 and n = 4,

return `1->4->3->2->5->NULL`.

Note:  
Given m, n satisfy the following condition:  
1 ? m ? n ? length of list.

思路：由于要求one-pass，这里就不能使用简单化的操作了，如果没有这个要求，我们可以找到m到n的这段链表，然后进行反转，然后标记链接即可。有这个要求之后就必须在M到n之间进行转换。尤其注意从第一个节点开始反转

#include <iostream> 
    #include <vector>
    #include <string>
    using namespace std;
    typedef struct list_node List;  
    struct list_node  
    {  
        struct list_node* next;  
        int value;  
    };  
      
    void print_list(List* list)  
    {  
        List* tmp=list;  
        while(tmp != NULL)  
        {  
            cout<<tmp->value<<endl;  
            tmp = tmp->next;   
        }  
    }  
      
    /* 
    初始化List  将从1~n的数字插入到链表中  
    */  
    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;  
            }  
        }  
    }  
      
    int Len_list(List* list)  
    {  
        if(list == NULL)  
            return 0;  
        else  
            return Len_list(list->next)+1;  
    }  
    
    // 将链表中的第m个节点到第n个节点之间的元素进行反转 
    void ReverseList(List*& list,int m,int n)  
    {
    		if(list == NULL || list->next == NULL || n-m<=1) 
    			return ;
    		int num=1;
    		List* pre,*next,*cur,*tmp,*temp;
    		cur= list;
    		pre = NULL;
    		while(cur != NULL)
    		{
    			next = cur->next;
    			if(num < m)
    			{
    				pre = cur;
    				cur = next;
    			}
    			if(num == m)
    			{
    				tmp = cur;
    				temp = cur;
    				cur = next;			 
    			}
    				
    			if(num >m && num <= n)
    			{
    				cur->next = temp;
    				temp = cur;
    				cur = next;			 
    			}
    			if(num == n)
    			{
    				if(m ==1)
    					list = temp;
    				else
    					pre->next = temp;					
    				tmp->next = cur;
    				break;
    			}
    			num++;
    		}
    } 
    
    int main() 
    {
    	int array[]={5,1,2,7,8,4,3,6,10,9};
    	//int array[]={1,4,3,2,5,2};
    	List* list;
    	Init_List(list,array,sizeof(array)/sizeof(int));
    	ReverseList(list,1,3);
    	print_list(list);
    	return 0;
    }