单链表按k值重新排序

梦里梦外; 2022-07-24 11:06 148阅读 0赞

## 单链表按k值重新排序 ##

题目要求：  
给定一链表头节点，节点值类型是整型。  
现给一整数k，根据k将链表排序为小于k，等于k，大于k的一个链表。  
对某部分内的节点顺序不做要求。

--------------------

## 算法思路分析及代码(C) ##

思路：将链表分为小于k、等于k、大于k的三个链表，然后再合并。

--------------------

链表结点定义：

typedef struct Node
    {
        int data;
        struct Node* next;
    }node, *pNode;

--------------------

算法代码：

pNode sortLinkedList(pNode head, int k)
    {
        pNode sHead = NULL;//小头
        pNode sTail = NULL;//小尾
        pNode eHead = NULL;//等头
        pNode eTail = NULL;//等尾
        pNode bHead = NULL;//大头
        pNode bTail = NULL;//大尾
    
        pNode temp = NULL;
        //拆分链表
        while (head != NULL)
        {
            temp = head->next;
            head->next = NULL;
    
            if (head->data < k)
            {
                if (!sHead){
                    sHead = head;
                    sTail = head;
                }
                else{
                    sTail->next = head;
                    sTail = head;
                }
            }
            else if (head->data == k)
            {
                if (!eHead){
                    eHead = head;
                    eTail = head;
                }
                else{
                    eTail->next = head;
                    eTail = head;
                }
            }
            else
            {
                if (!bHead){
                    bHead = head;
                    bTail = head;
                }
                else{
                    bTail->next = head;
                    bTail = head;
                }
            }
            head = temp;
        }
    
        //合并链表
        if (sTail)
        {
            sTail->next = eHead;
            eTail = (eTail == NULL ? sTail : eTail);
        }
    
        if (eTail)
        {
            eTail->next = bHead;
        }
        return sHead != NULL ? sHead : (eHead != NULL ? eHead : bHead);
    }