Linked list exchange and sorting

1. Given a linked list, two adjacent nodes are exchanged, and the exchanged linked list is returned.

Example: given 1 - > 2 - > 3 - > 4, you should return 2 - > 1 - > 4 - > 3

explain:

• Your algorithm can only use the extra space of constants.
• You can't simply change the value inside the node, but you need to actually exchange nodes.

 1 class Solution {
 2 public:
 3     ListNode* swapPairs(ListNode* head) {
 4         ListNode *dummy = new ListNode(-1), *pre = dummy;
 5         dummy->next = head;
 6         while (pre->next && pre->next->next) {
 7             ListNode *t = pre->next->next;
 8             pre->next->next = t->next;
 9             t->next = pre->next;
10             pre->next = t;
11             pre = t->next;
12         }
13         return dummy->next;
14     }
15 };

2. The head and tail nodes are staggered.

**Given a single linked list L, * * original node order: L0 → L1 →... → Ln-1 → Ln; Write an algorithm and change the node order to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 →..., that is, the head and tail nodes are staggered.

Solution: 1. The fast and slow pointer finds the middle point and divides the original linked list into two sections; 2. Store the following linked list elements in the stack; 3 - traverse the stack and insert the top elements of the stack into the appropriate position of the previous linked list in turn.

void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        //The fast and slow pointer finds the midpoint of the linked list and disconnects it
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *right = slow->next;
        slow->next = nullptr;
        //Press the linked list on the right into the stack
        stack<ListNode *> s;
        while (right) {
            s.push(right);
            right = right->next;
        }
        ListNode *current = head;
        while (!s.empty()) {
            //Take out the top element of the stack
            ListNode *top = s.top();
            s.pop();
            ListNode *next = current->next;
            current->next = top;
            top->next = next;
            current = next;
        }
    }

If the topic requires no additional storage space, first find the middle position with the fast and slow pointer, divide it into two linked lists, then reverse the second linked list, and finally insert the reversed linked list into the first linked list one by one.

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        ListNode* slow = head;
        ListNode* fast = head;

        while(slow && fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = reverseList(slow->next);
        ListNode* p = head;
        while(slow->next)
        {
            ListNode* tmp = slow->next;
            slow->next = tmp->next;

            tmp->next = p->next;
            p->next = tmp;
            p = tmp->next;
        }
    }

private:
    ListNode* reverseList(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* p = head;
        ListNode* newHead = head;

        while(p->next)
        {
            ListNode* tmp = p->next;
            p->next = tmp->next;
            tmp->next = newHead;
            newHead = tmp;
        }

        return newHead;
    }
};

3. Single linked list sorting

Title: give you the head node of the linked list. Please arrange it in ascending order and return the sorted linked list. The linked list is sorted under O(n log n) time complexity and constant o(1) space complexity

Input: head = [4,2,1,3]
Output:[1,2,3,4]

The specific methods are as follows.

• First get the length of the linked list, and then split the linked list into sub linked lists for merging.

• subLength is used to represent the length of the sub linked list to be sorted each time. Initially, subLength=1.

• Each time, the linked list is divided into several sub linked lists with a length of subLength (the length of the last sub linked list can be less than subLength), and each two sub linked lists are combined in a group. After the combination, several sub linked lists with a length of subLength can be obtained × 2 (the length of the last sublist can be less than subLength) × 2). Merging two sub linked lists still uses the method of merging two ordered linked lists.

• Double the value of subLength, repeat step 2, and merge the longer ordered sub linked list until the length of the ordered sub linked list is greater than or equal to length, and the whole linked list is sorted.

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode* prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* next = nullptr;
                if (curr != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};