重排链表

问题描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

例子：

解题思路

第一个想到的就是分离再合并的方法：
①将链表分成前部分和后部分；
②将后部分反转顺序；
③合并前后部分。

示意图：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int length(ListNode* head){//求链表的长度
        int n=0;
        while(head){
            n++;
            head = head->next;
        }
        return n;
    }

    void hebing(ListNode* l1,ListNode* l2){ //合并链表
        while(l1 && l2){
            ListNode* q = l1->next;
            ListNode* p = l2->next;
            l1->next = l2;
            l1 = q;
            if(!l1) break;
            l2->next = q;
            l2 = p;
        }
    }

    void reorderList(ListNode* head) {
        if(!head || !head->next) return ;
        int mid = length(head)/2;
        ListNode* cur = head;
        ListNode* hou;
        int i=0;
        while(cur){//分离链表
            i++;
            if(i<mid){
                cur = cur->next;
            }else if(i == mid || i == mid+1){
                ListNode* temp = cur->next;
                hou = cur;
                cur->next = nullptr;
                cur = temp;
            }else{ //将后半段反序
                ListNode* q = cur->next;
                cur->next = hou;
                hou = cur;
                cur = q;
            }
        }
        hebing(head,hou);
    }
};

时间复杂度：O（n）
空间复杂度：O（1）

对链表进行插入排序

问题描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

解题思路

按照插入排序的算法步骤来写即可：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next)//若链表为空或只有一个结点不需要排序
            return head;
        ListNode* pre_head = new ListNode(0,head);
        ListNode* last = head;
        ListNode* curr = head->next;
        while (curr) {
            if (last->val <= curr->val) {//若当前结点的值大于排好序的最后一个值，则直接插在其后
                last = last->next;
            } else {//否则，从头遍历，找到合适的位置插入
                ListNode *prev = pre_head;
                while (prev->next->val <= curr->val)
                    prev = prev->next;
                last->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = last->next;
        }
        return pre_head->next;
    }
};

心得

好像开始会写链表的题了，就是解题慢了些。