My accepted C++ code using stack


  • 1
    L
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
            ListNode *mid, *end;
            stack<ListNode *> nodestack;
            mid = head;
            end = head;
            if(head == NULL || head->next==NULL || head->next->next == NULL) return;
            while(end->next!=NULL && end->next->next != NULL)
            {
                mid = mid->next;
                end = end->next->next;
            }
            ListNode *L1 = head;
            ListNode *L2 = mid->next;
            while(L2!=NULL)
            {
                nodestack.push(L2);
                L2=L2->next;
            }
            mid->next = NULL;
            while(!nodestack.empty())
            {
                L2 = nodestack.top();
                nodestack.pop();
                L2->next = L1->next;
                L1->next = L2;
                L1 = L2->next;
            }
            return;
        }
    };

Log in to reply
 

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