#include <stdlib.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * @author Senky
 * @date 2023.03.23
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 将数据重新排列不影响链表的位置
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
int compar(const void* p1, const void* p2)
 {
    return (  (*(int*)p1) -
              (*(int*)p2)   );
 }

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
   int n = 0;//链表长度

   struct ListNode* p = pHead1;
   int flag = 1;
   /*记录两个链表的总结点数*/
   while(p)
   {
        n++;
        if(p ->next == NULL && flag)
        {
            /*
             *第一次p->next为NULL时p在pHead1的表尾,
             *第二次p->next为NULL时p在pHead2的表尾,
             *第二次应该直接退出循环,否则链表形成了环
             */
            p->next = pHead2;
            flag = 0;
           
        }
            p = p->next;
   }

    int i = 0;
    int* str = malloc(n*sizeof(int));
    /*str数组记录两个链表的数据域*/
    {
        p = pHead1;
        while(p)
        {
            str[i++] = p->val;
            p = p->next;
        }
        /*将数组排序*/
        qsort(str, n, sizeof(str[0]),  compar);
    }
    
    {
        /*将排序好的数据写回链表中*/
        p = pHead1;
        i = 0;
        while(p)
        {
            p->val = str[i++];
            p = p->next;
        }
    }

    return pHead1;
}

图解：