当前位置:   article > 正文

链表OJ6——链表分割(C++代码实现)

oj6

声明:我的链表OJ系列是针对无头单向不循环链表的题目

题目

题目来源:链表分割_牛客题霸_牛客网

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针

思路

创建两个链表,遍历一遍传入的链表,将值大于x的结点和值小于x的结点依次尾插到两个链表中,最后再将这两个链表链接起来,并返回第一个结点的位置即可。

1.把小于x的结点尾插到less链表,把大于x的结点尾插到greater链表。

2.将less链表与greater链表链接起来。

 注意:
1.链接后的链表的最后一个结点的指针域需要置空,否则可能造成链表成环。
2.返回的头指针应是lessHead->next,而不是lessHead。

  1. struct ListNode {
  2. int val;
  3. struct ListNode *next;
  4. ListNode(int x) : val(x), next(NULL) {}
  5. };
  6. class Partition {
  7. public:
  8. ListNode* partition(ListNode* pHead, int x) {
  9. ListNode* greaterHead, *greaterTail, *lessHead, *lessTail;
  10. //申请一个头结点,后面链接大于x的结点
  11. greaterHead = greaterTail = (ListNode*)malloc(sizeof(struct ListNode));
  12. //申请一个头结点,后面链接小于x的结点
  13. lessHead = lessTail = (ListNode*)malloc(sizeof(struct ListNode));
  14. greaterTail->next = NULL;//尾指针的指针域置空
  15. lessTail->next = NULL;//尾指针的指针域置空
  16. ListNode* cur = pHead;//接收传入的链表,准备遍历
  17. while (cur)
  18. {
  19. if (cur->val < x)
  20. {
  21. //结点值小于x,链接到less链表后面
  22. lessTail->next = cur;
  23. lessTail = lessTail->next;
  24. }
  25. else
  26. {
  27. //结点值大于x,链接到greater链表后面
  28. greaterTail->next = cur;
  29. greaterTail = greaterTail->next;
  30. }
  31. cur = cur->next;//指针后移,遍历后面的结点
  32. }
  33. //将less链表和greater链表链接起来
  34. lessTail->next = greaterHead->next;//greater链表的第一个结点链接到less链表的尾上
  35. greaterTail->next = NULL;//将greater链表最后一个结点的指针域置空
  36. ListNode* head = lessHead->next;//接收链接后链表的第一个结点地址
  37. free(greaterHead);//释放greater链表的头结点
  38. free(lessHead);//释放less链表的头结点
  39. return head;//返回新链表
  40. }
  41. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/941382
推荐阅读
相关标签
  

闽ICP备14008679号