链表交换和排序

1、给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		if (head == nullptr || head->next == nullptr)
			return head;
		ListNode* res = head->next;
		ListNode* pre = nullptr;
		ListNode* tmp = nullptr;
		while (head!=nullptr&&head->next != nullptr) {
			tmp = head->next;
			head->next = head->next->next;
			tmp->next = head;
			if (pre != nullptr) {
				pre->next = tmp;
				pre = head;
			}
			else
				pre = head;
			head = head->next;
		}
		if (head)
			pre->next = head;
		return res;
	}
};

2、首尾节点交错连接。

给定一个单链表 L，原节点顺序：L0→L1→…→Ln-1→Ln；编写一个算法，将节点顺序变更为：L0→Ln→L1→Ln-1→L2→Ln-2→…，即首尾节点交错链接。

题解：1，快慢指针找中点将原链表切分两段；2，将后面的链表元素存入栈中；3-遍历栈依次将栈顶元素插入到前面的链表合适的位置。

void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        //快慢指针找到链表中点并断开
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *right = slow->next;
        slow->next = nullptr;
        //将右边的链表压入栈中
        stack<ListNode *> s;
        while (right) {
            s.push(right);
            right = right->next;
        }
        ListNode *current = head;
        while (!s.empty()) {
            //取出栈顶元素
            ListNode *top = s.top();
            s.pop();
            ListNode *next = current->next;
            current->next = top;
            top->next = next;
            current = next;
        }
    }

如果题目要求不用额外的存储空间的话：先用快慢指针找到中间位置，将其分成两个链表， 再将第二个链表反转， 最后将反转的链表挨个插入第一个链表。

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、单链表排序

题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。在 O(n log n) 时间复杂度和常数级o(1)空间复杂度下，对链表进行排序.

输入：head = [4,2,1,3]
输出：[1,2,3,4]

具体做法如下。

• 首先求得链表的长度length，然后将链表拆分成子链表进行合并。

• 用 subLength 表示每次需要排序的子链表的长度，初始时subLength=1。

• 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用合并两个有序链表的做法。

• 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完毕。

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;
    }
};