Article From:

Original website:

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


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


Turn over in one place


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:, 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.
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }

class Solution {
     * @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.
    while(j<n)//Find the first N node of the original chain.

    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;
    //renexNTo reverse part of the head, you should mount it to the left part of the original list.
    if (leftNodes==NULL)
        return 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 *