专栏首页光城(guangcity)​精益求精单链表归并排序与快速排序

​精益求精单链表归并排序与快速排序

精益求精单链表归并排序与快速排序

0.导语

本节主要阐述自顶向下与自底向上的归并排序,以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。

1.自底向上的归并排序

归并排序是最适合单链表排序的算法,因为两个链表的归并比较简单,和数组的归并过程思路相同。

bottom-to-up 的归并思路:先两个两个的 merge,完成一趟后,再 4 个4个的 merge,直到结束。

例如:[4,3,1,7,8,9,2,11,5,6].

step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)step=2: (1->3->4->7)->(2->8->9->11)->(5->6)step=4: (1->2->3->4->7->8->9->11)->5->6step=8: (1->2->3->4->5->6->7->8->9->11)

首先编写两个链表的合并程序:

非递归实现

/**
 * 非递归合并
 * @param l1
 * @param l2
 * @return
 */
ListNode* __merge(ListNode* l1, ListNode* l2) {
    ListNode* dummyHead = new ListNode(0),*p=dummyHead;
    while(l1&&l2) {
        if(l1->val<l2->val) {
            p->next=l1;
            p=l1;
            l1=l1->next;
        } else {
            p->next=l2;
            p=l2;
            l2=l2->next;
        }
    }
    p->next = l1?l1:l2;
    p=dummyHead->next;
    delete dummyHead;
    return p;
}

递归实现

/**
 * 递归合并
 * @param l1
 * @param l2
 * @return
 */
ListNode* merge(ListNode* l1,ListNode* l2)
{
    if(l1==NULL)
    {
        return l2;
    }
    if(l2==NULL)
    {
        return l1;
    }
    if(l1->val < l2->val)
    {
        l1->next=merge(l1->next,l2);
        return l1;
    }
    else
    {
        l2->next=merge(l2->next,l1);
        return l2;
    }
}

对于链表的归并合并与数组归并合并区别,我们会发现链表不能像数组那样根据index去快速索引到相应位置上的值,那么在对链表进行归并排序的时候,就需要确定那两个列表进行归并,然后调用上述merge进行合并即可。

对于一个链表如下:假设sort1为合并列表1的head,sort2为合并列表2的head,那么我们关键就是找出每次合并的这个head即可。

3       4    5     7    8   10
sort1       sort2

因此这里写出一个获取head的函数:其中head为当前传进来的链表头结点,sz为几路归并。

ListNode* getHead(ListNode* head, int sz) {
    ListNode* p = head;
    while(p&&--sz)
        p=p->next;
    // 此时p指向的是从head数满足sz个节点的位置
    
    if(!p) return p;
    // 返回下一个待归并sort1的头节点
    ListNode* next = p->next;
    // 断开尾部
    p->next=NULL;
    return next;
}

最后,来编写一下自底向上的归并排序函数:

/**
 * 自底向上的归并排序
 * @param head
 * @return
 */
ListNode* sortList(ListNode* head) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* p = head;
    int n = 0;
    // 获取链表总长度
    while (p) {
        ++n;
        p = p->next;
    }
    for (int sz = 1; sz <= n; sz+=sz) {
        ListNode* cur = dummyHead->next;
        ListNode* tail=dummyHead;
        while(cur) {
            ListNode* sort1Head = cur;
            ListNode* sort2Head = getHead(sort1Head,sz);
            cur = getHead(sort2Head,sz); // left->@->@->@  right->@->@->@...
            tail->next = __merge(sort1Head,sort2Head); // left->@->@->@  right->@->@  cur->@->@...
            // tail指向合并链表末尾
            while(tail->next) {
                tail=tail->next;
            }

        }
    }
    p=dummyHead->next;
    delete dummyHead;
    return p;
}

2.自顶向下的归并排序

自顶向下的归并排序需要注意的是:如何找到链表的中点?

通过2个快慢指针,快指针每一步走2个节点,慢指针每一步走1个节点,当快指针到达链表尾部时,慢指针到达链表的中间节点。

/**
 * 自顶向下的归并排序
 * @param head
 * @return
 */
ListNode* sortList(ListNode* head) {
    return __mergesort(head);
}
ListNode* __mergesort(ListNode* node)
{
    if(!node || !node->next) return node;
    ListNode *fast=node;//快指针走两步
    ListNode *slow=node;//慢指针走一步
    ListNode *brek=node;//断点
    while(fast && fast->next)
    {
        fast=fast->next->next;
        brek=slow;
        slow=slow->next;
    }
    brek->next=nullptr;
    ListNode *l1=__mergesort(node);
    ListNode *l2=__mergesort(slow);
    //合并[node...brek] [slow...fast]
    return merge(l1,l2);
}

3.改变链接的快速排序

改变链接的指向思路:

  • 将比枢椎(这里选择第一个节点)小的值,链接到一个小于枢椎的链表中;
  • 比枢椎大的值,链接到一个大于枢椎的链表中;
  • 将小于枢椎值的链表,枢椎节点,大于枢椎值的链表链接起来。

对一段链表执行划分过程时,头节点可能发生改变以及终止节点可能是非空的,因此对一段链表的划分过程需要给出:前驱节点

/**
 * 快排(改变链接)
 * @param head
 * @return
 */
ListNode* sortList(ListNode* head) {
    ListNode dummyHead(0);
    dummyHead.next=head;
    quickSort(&dummyHead, head, NULL);
    return dummyHead.next;
}
void quickSort(ListNode* dummyHead, ListNode* head, ListNode* tail) {
    if(head!=tail) {
        ListNode *pivot = Partation(dummyHead, head);
        quickSort(dummyHead, dummyHead->next, pivot);
        quickSort(pivot, pivot->next, tail);
    }
};

ListNode* Partation(ListNode* dummyHead, ListNode* head) {
    int pivot = head->val; // 选第一个节点为枢椎
    ListNode nodeL(0), nodeR(0);
    ListNode* pleft = &nodeL,* pright = &nodeR,* p = head->next;
    while (p) {
        if (p->val < pivot) {
            pleft->next = p;
            pleft = p;
        } else {
            pright->next = p;
            pright = p;
        }
        p=p->next;
    }
    // 大于枢椎的链表连接尾部NULL
    pright->next = NULL;
    // 小于枢椎的链表连接head
    pleft->next = head;
    // head链接大于枢椎的链表第一个节点
    head->next = nodeR.next;
    // 更新实际返回链表的头节点指向
    dummyHead->next = nodeL.next; // 链表头节点
    return head;
};

4.改变值的快速排序

改变值的快速排序思想:由于链表只能顺序索引,故不能使用数组划分的方法。将比枢椎小的节点的值,依次和枢椎后的节点的值交换。如 5->3->6->4->7->2 则 5 为枢椎3 < 5: swap(3, 3) ,(起始交换位置为基元的下一个节点,即第2个节点) 6 > 5: continue; 4 < 5: swap(6, 4) (交换位置后移,交换4和第3个节点的值) 7 > 5: continue 2 < 5: swap(4, 2) (交换位置后移,交换2和第4个节点的值)

循环结束 swap(5, 2) (交换枢椎值和第4个节点的值)。

/**
 * 快速排序(改变值)
 */
ListNode *partition(ListNode *head){
    int pivot = head->val;
    ListNode *slow=head, *fast=head->next;
    while(fast){
        if(fast->val < pivot){
            slow = slow->next;
            swap(slow->val, fast->val);
        }
        fast=fast->next;
    }
    swap(head->val, slow->val);
    return slow;
}
void quickSort(ListNode *head, ListNode *tail){
    if(head!=tail){
        ListNode *pivot = partition(head);
        printLinkedList(head);
        quickSort(head, pivot);
        quickSort(pivot->next, tail);
    }
}
ListNode* sortList3(ListNode* head) {
    quickSort(head, nullptr);
    return head;
}

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 精益求精解LeetCode(82与83)

    好久没有刷题与更文了,今天来一场LeetCode上面简单与中等题目多种方法刷题。

    公众号guangcity
  • LeetCode攀登之旅(1)

    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

    公众号guangcity
  • win7+ kali linux双系统 + 无线路由WiFi破解

    本篇文章写于本科大二下学期,本篇文章目的是攻破隔壁老王wifi密码,实现wifi路由密码的破解,所采用的的系统为linux中的kali,实现为win7+kali...

    公众号guangcity
  • 【leetcode刷题】T104-翻转链表

    木又AI帮
  • Leetcode 142 Linked List Cycle II

    Given a linked list, return the node where the cycle begins. If there is no cyc...

    triplebee
  • Leetcode 24. Swap Nodes in Pairs

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 两两交换链表中的节点

    一份执着✘
  • 链表总计

    // 这里创建一个新的链表,是因为必须创建一个指针,来输出结果集,或者只新建一个指针来保证记录链表的关系也可。

    用户7625070
  • LeetCode 每日一题206: 反转链表

    按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

    benny
  • LeetCode 24 Swap Nodes in Pairs

    ShenduCC

扫码关注云+社区

领取腾讯云代金券