首页 > 编程 > C++ > 正文

C++实现单链表按k值重新排序的方法

2020-01-26 14:10:03
字体:
来源:转载
供稿:网友

本文实例讲述了C++实现单链表按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);}

希望本文所述对大家C++程序设计有所帮助。

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表