In this Leetcode Reverse Linked List II problem solution we have Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from the position left to position right, and return the reversed list.

Leetcode Reverse Linked List II problem solution


Problem solution in Python.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        counts = 0
        stack = []
        dummy = ListNode(0)
        pre = dummy
        while head:
            counts += 1
            if counts < m:
                pre.next = head
                pre = pre.next
            elif counts >=m and counts <=n:
                stack.append(head)
            else:
                break
            head = head.next

        while stack:
            pre.next = stack.pop()
            pre = pre.next
        pre.next = head

        return dummy.next



Problem solution in Java.

public ListNode reverseBetween(ListNode head, int m, int n) { 
        ListNode preRev = null;
        ListNode curr = head;
        int i = 1;
        while(i<m) { preRev = curr; curr = curr.next; i++; }
        
        ListNode end = curr;     
        ListNode pre = null; 
        while(i<=n) {
         ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
            i++;
        }
        
        end.next = curr;
        if(preRev != null) preRev.next = pre;
        return preRev == null ? pre: head;    
    }


Problem solution in C++.

ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(!head->next || m == n) return head;
        ListNode* l = head;
        for(int i = 0; i < m-2; i++) l = l->next;
        
        ListNode* pre = NULL;
        ListNode* cur = m == 1 ? l : l->next;
        ListNode* next = cur->next;
        ListNode* reverseHead = cur;
        for(int i = 0; i < n-m+1; i++){
            cur->next = pre;
            pre = cur;
            cur = next;
            next = next ? next->next : NULL;
        }
        reverseHead->next = cur;
        if(m != 1) l->next = pre;
        return m == 1 ? pre : head;
    }


Problem solution in C.

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if(!head->next) return head;
    if(m == n)return head;
    if(!head->next->next){
        struct ListNode* tmp = head->next;
        head->next->next = head;
        head->next = NULL;
        return tmp;
    }
    struct ListNode* revtail;
    struct ListNode* orghead;
    struct ListNode* scanner = head;
    struct ListNode* before = NULL;
    int counter = 0;
    while(counter++ < m - 1){
        before  = scanner;
        scanner = scanner->next;
    }
    
    orghead = before;
    before = scanner;
    struct ListNode* curr = scanner->next;
    struct ListNode* curr_next = NULL;
    
    revtail = scanner;
    counter = 0;
    while(counter++<(n - m)){
        curr_next = curr->next;
        curr->next = before;
        before = curr;
        curr = curr_next;
    }
    
    if(orghead)
       orghead->next = before;
    
    revtail->next = curr;
    
    return orghead == NULL ? before : head;
}