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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment