Tag:Lintcode C++ chain list
Category:Lintcode
Article From:https://www.cnblogs.com/Tang-tangt/p/9063518.html

Original website: https://www.lintcode.com/zh-cn/old/problem/reverse-linked-list-ii/#

36. Flip list II

 

Discussion area

Flip the M node from the list to the part of the N node.

 Matters needing attention

m,nMeet the length of 1 < < m < < < n > chain table

Sample

Give the list1->2->3->4->5->null, m = 2 And N = 4, return1->4->3->2->5->null

Challenge 

Turn over in one place

Label 

linked list
 
Train of thought: through the while cycle, find the M node and the N node of the linked list. Then, through the three pointer to flip the middle node in m~n, the idea of turning in situ can refer to the flip list: http://www.cnblogs.com/Tang-tangt/P/8709167.html, the difference is that the initial value of the subsequent node is not NULL, but is equal to the original list m+1 node.
       When the flipping is completed, it is judged whether the original list n-1 is empty, and if not empty, the linked list after the flip is mounted to the end of the N-1 node, and if it is empty, the flip list is returned directly.
 
ACCode:
/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    ListNode * reverseBetween(ListNode * head, int m, int n) {
        // write your code here
        if (head==NULL)
    {
        return head;
    }

    ListNode * leftNodes=NULL;
    ListNode *rightNodes=head;
    ListNode * cur=head;
    
    int i=1,j=i,count=0;
    while(i<m)//Find the first m node of the original chain.
    {
        leftNodes=cur;
        cur=cur->next;
        i++;
    }
    while(j<n)//Find the first N node of the original chain.
    {
        rightNodes=rightNodes->next;
        j++;
    }
    rightNodes=rightNodes->next;

    
    ListNode * rePre=cur;
    ListNode *renexN=rightNodes;//Part of the tail part should be mounted on the right part of the original list.
    while(rePre!=rightNodes)//Flipping m~n nodes;
    {
        rePre=cur->next;
        cur->next=renexN;
        renexN=cur;
        cur=rePre;
    }
    
    //renexNTo reverse part of the head, you should mount it to the left part of the original list.
    if (leftNodes==NULL)
    {
        
        return renexN;
    }

    leftNodes->next=renexN;
    return head;
    }
};

 

 
 
 
Link of this Article: 36 flip list II

Leave a Reply

Your email address will not be published. Required fields are marked *