0ms c++ solution and iteratively


  • 0
    L

    First we find where the reversed link-list should start. Then build a new node, node->next points to the latest node of the original link list. At last, link the 3 part together.

    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            ListNode* p1 = head;
            ListNode node(0);
            ListNode* p2 = &node;
            ListNode* prev = NULL;
            while(p1 && --m > 0)
            {
            	prev = p1;
            	p1 = p1->next;
            	n--;
            }
            while(p1 && n-- > 0)
            {
            	ListNode* tmp = p2->next;
            	p2->next = p1;
            	p1 = p1->next;
            	p2->next->next = tmp;
            }
            if(prev)
            	prev->next = node.next;
            else
            	head = node.next;
           	p2 = &node;
            while(p2->next)
            	p2 = p2->next;
            p2->next = p1;
            return head;
        }
    };

Log in to reply
 

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