Why nobody does it with recursion, shouldn't the code be simpler?


  • 5
    W
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(m==n){
                return head;
            }
            if(m>1){
                ListNode newHead = head;
                newHead.next = reverseBetween(head.next, m-1, n-1);
                return newHead;
            }else{
                ListNode next = head.next;
                ListNode newHead = reverseBetween(next, 1, n-1);
                ListNode nextnext = next.next;
                next.next = head;
                head.next = nextnext;
                return newHead;
            }
        }
    }
    

  • 1
    E

    Brilliant solution!
    I rewrote it with C++, here is my code:

    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) 
        {
            if(m == n)
                return head;
            
            if(m > 1)
            {
                head->next = reverseBetween(head->next, m - 1, n - 1);
                return head;
            }
            else
            {
                auto tailNode = reverseBetween(head->next, 1, n - 1);
                auto tailNodeNext = head->next->next;
                
                head->next->next = head;
                head->next = tailNodeNext;
    
                return tailNode;
            }
        }
    };
    

  • 0
    Z

    Could you please explain the part where m > 1, thanks a lot.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.