My C++ implementation (using two pairs of pointers to assist the insertion of the reversed sub-list)


  • 0
    D
    /*In this implementation,two pairs of pointers are used: one (revHead/revTail) to save the head/tail of the reversed sub-list, and the other (startPos/endPos) to save the insert positions in the original list.
    A dummy head node is used to track the real head node.*/
         ListNode *reverseBetween(ListNode *head, int m, int n) {
                ListNode dummyHead(0), *revHead, *revTail, *startPos, *endPos, *pNode ;
                int i;
                
                dummyHead.next = head; // use a dummy node to point to the real head
                
                // search for the (m-1)-th node, where 0-th node is the dummy head node 
                head = &dummyHead;
                revHead = head;
                for(i=1;i<m; i++) head = head->next;
                startPos = head; // the node that is precedent to the head of the reversed sub-list
                head = head->next; // move to the first to-be-reversed node
                revTail = head;  // , which is also the last node of the reversed sub-list (after reversion)
                
                // do the reverse work, go through each to-be-reversed node
                for(i=m;i<=n;i++)
                {
                    pNode = head->next;
                    head->next = revHead; // link it as a precedent node of the previous to-be-reversed node
                    revHead = head;
                    head = pNode;
                }
                endPos = head; // the first node after the reversed sub-list 
                
                // cut the reversed sub-list and link it back to the original list
                startPos->next = revHead;
                revTail->next = endPos;
                
                return dummyHead.next;
                
            }

Log in to reply
 

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