56ms, accepted c++ solution


  • 0
    P
    class Solution {
    public:
        void reorderList(ListNode* head) {
            // cut list   1->2->3->4->5 ==> list1:1->2 list2:3->4->5
            ListNode *fast = head, *slow = nullptr;
            while (fast != nullptr && fast->next != nullptr) {
            	fast = fast->next->next;
            	slow = slow == nullptr ? head : slow->next;
            }
            if (slow == nullptr) return;
            ListNode *head2 = slow->next;
            slow->next = nullptr;
            // reverse list2  3->4->5  ==>  5->4->3
            slow = fast = head2;
            head2 = nullptr;
            while (fast != nullptr) {
                fast = fast->next;
            	slow->next = head2;
            	head2 = slow;
            	slow = fast;
            }
            // merge two list  list1:1->2 list2:5->4->3  ==> 1->5->2->4->3
            slow = fast = head;
            while (fast != nullptr && head2 != nullptr) {
            	fast = fast->next;
            	slow->next = head2;
            	head2 = head2->next;
            	slow->next->next = fast ? fast : head2;
            	slow = fast;
            }
        }
    };
    

  • 0
    A

    @Paynepein said in 56ms, accepted c++ solution:

        slow = fast = head2;
        while (fast->next != nullptr) {
        	fast = fast->next;
        	slow->next->next = slow;
        	slow = fast;
    

    Are you sure this is correct? I don't need to try but I can tell this is definitely dead loop.


  • 0
    P

    @ayuanx When the fast pointer points to the last node, the execution is out of the loop.


  • 0
    A

    @Paynepein Man, you should put it into the test if you don't know what I was talking about.


  • 0
    P

    @ayuanx Yes, You're right, I'm sorry for not testing the code, thank you very much!


Log in to reply
 

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