Reverse Linked List II Problem Solution

Reverse Linked List II Problem: Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

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;
}