首页 > C语言的单链表分割

C语言的单链表分割

已知链表头指针head与数值x，将所有小于x的节点放在大于或等于x 的节点前，且保持这些节点的原来的相对位置。

在这里插入图片描述

这个过程有点类似于快速排序，寻找一个阈值，比该阈值小的放左边，比该阈值大的放右边。只是由数组遍历变为来链表遍历，操作变成了指针的指向。

具体步骤如下:

  1. 创建一个less_ptr，负责对less端的链表进行维护
  2. 创建一个more_ptr，负责对more端的链表进行维护
  3. 最终进行less的尾和more的头进行合并，返回头节点。

这个过程需要注意保存less端和more端的头节点,算法实现如下

Data *part_list(Data *head, int n) { Data less_head;Data more_head;less_head.data = 0;less_head.next = NULL;more_head.data = 0;more_head.next = NULL;Data *less_ptr = &less_head;Data *more_ptr = &more_head;/*遍历链表，将大于n的放在右端，小于等于n的放在左端*/while(head) { if(head->data > n){ more_ptr->next = head;more_ptr = head;} else { less_ptr->next = head;less_ptr = head;}head = head->next;}/*连接小端的尾和大端的头，并将大端的尾置空*/less_ptr->next = more_head.next;more_ptr->next = NULL;/*返回小端的头，因为此时它是链表的表头*/return less_head.next;
}

源代码测试如下:

#include 
#include typedef struct Link_list
{ /* data */int data;struct Link_list *next;
}Data;/*打印链表*/
void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}/*尾插法创建链表*/
Data *insert_tail(Data *head, int n) { head = (Data *)malloc(sizeof(Data));head->next = NULL;Data *r = head;int b;while(n--){ scanf("%d",&b);Data *p = (Data *)malloc(sizeof(Data));p->data = b;r->next = p;p->next = NULL;r = p;}return head;
}/*分割链表*/
Data *part_list(Data *head, int n) { Data less_head;Data more_head;less_head.data = 0;less_head.next = NULL;more_head.data = 0;more_head.next = NULL;Data *less_ptr = &less_head;Data *more_ptr = &more_head;while(head) { if(head->data > n){ more_ptr->next = head;more_ptr = head;} else { less_ptr->next = head;less_ptr = head;}head = head->next;}less_ptr->next = more_head.next;more_ptr->next = NULL;return less_head.next;
}int main(){ Data *head;int i ,b ;printf("construct link list :
");head = insert_tail(head,5);Data *test = head -> next;print_list(test);printf("after part list :
");/*设置3为阈值，大于3的都放在右端，小于等于3的都放在左端*/Data *part = part_list(head->next,3);print_list(part);return 0;
}

输出如下:

construct link list :
5 4 3 2 1
5 4 3 2 1 
after part list :
3 2 1 5 4

更多相关：

  • 剑指offer：面试题35. 复杂链表的复制

    题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...

  • leetcode-86 分隔链表

    给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...

  • leetcode-142 环形链表II

    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...

  • leetcode-92 反转链表II

    题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...

  • leetcode-206 反转链表

    描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...

  • python制作统计图_刻意练习11：Python描述统计、简单统计图形

    学习计划 MyPlan11 主题：Python描述统计、简单统计图形 时间：8.5-8.11周内完成 参考资料：新书《谁说菜鸟不会数据分析python篇》 各位星友们，在这个星球里每个人都要逼迫自己学习未知的领域或知识点，每天进步一点点，积累的时间久了 ，菜鸟也能起飞。 完成情况： 在pandas中，使用describe函数进行描述统...

  • python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

    利用SocketServer模块来实现网络客户端与服务器并发连接非阻塞通信。 首先，先了解下SocketServer模块中可供使用的类： BaseServer：包含服务器的核心功能与混合（mix-in）类挂钩；这个类只用于派生，所以不会生成这个类的实例；可以考虑使用TCPServer和UDPServer。 TCPServer/UDPS...

  • 剑指offer：面试题37. 序列化二叉树

    题目：序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 示例:  你可以将以下二叉树：     1    /   2   3      /     4   5 序列化为 "[1,2,3,null,null,4,5]" 解题： /*** Definition for a binary tree no...

  • sd.js 2.0封装：更加简化请求传参内容

    sd.js  import $global from "./global"; import $g from "./sg"; import $ from "jquery"; import {Message, Loading} from "element-ui";//引入饿了么相关组件 import {Base64} from "js-...

  • sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

        原生sd.js----------------------------------------------------------------  const API_ROOT_URL = "http://www.api.com";const $d= {_postList_url: API_ROOT_URL + "/api...

©2024 11GX.COM