Share my solution


  • 0
    O
    /**
     * 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) {
            if (head == NULL) return;
            ListNode *middle = get_middle(head);
            ListNode *tmp = middle->next;
            middle->next = NULL;
            ListNode *b = reverse(tmp);
            merge(head, b);
        }
        
        ListNode* get_middle(ListNode *head) {
            if (head == NULL || head->next == NULL) return head;
            ListNode *slow = head, *fast = head->next;
            while (fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
        
        ListNode* reverse(ListNode *head) {
            if (head == NULL) return head;
            ListNode *p = head, *q = NULL;
            while (p != NULL) {
                ListNode *tmp = p->next;
                p->next = q;
                q = p;
                p = tmp;
            }
            return q;
        }
        
        ListNode* merge(ListNode *&a, ListNode *&b) {
            int cnt = 0;
            ListNode dummy(0);
            ListNode *p = &dummy;
            while (a != NULL && b != NULL) {
                if (cnt == 0) {
                    p->next = a;
                    a = a->next;
                } else {
                    p->next = b;
                    b = b->next;
                }
                p = p->next;
                cnt = 1 - cnt;
            }
            if (a != NULL) p->next = a;
            if (b != NULL) p->next = b;
            return dummy.next;
        }
    };

Log in to reply
 

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