/**
* 题目：将单向链表按某值划分成左边小、中间相等、右边大的形式
*
* 要求：
* 给定一个单向链表的头节点 head, 节点的值类型是整型， 再给定一个整数 privot。实现
*一个调整链表的函数， 将链表调整为左部分都是值小于privot的节点， 中间部分都是值等于privot
*的节点， 右部分都是值大于privot的节点。除这个要求外， 对调整后的节点顺序没有更多的要求。
*例如： 链表 9->0->4->5->1, privot=3。调整后链表可以是1->0->4->9->5, 也可以是
*0->1->9->5->4。总之， 满足左部分都是小千3的节点， 中间部分都是等于3的节点，右部分都
*是大于3的节点即可。对某部分内部的节点顺序不做要求。
*
* 分析：
* 解法的时间复杂度为 O(N), 额外空间复杂度为 O(N), 就是把链表中的所有节点放入一个额
*外的数组中， 然后统一调整位置的办法。具体过程如下：
* 1. 先遍历一遍链表， 为了得到链表的长度， 假设长度为N。
* 2. 生成长度为N的Node类型的数组 nodeArr, 然后遍历一次链表， 将节点依次放进 nodeArrray中。
* 3. 在 nodeArray中把小于 privot的节点放在左边， 把相等的放中间， 把大于的放在右边。
* 4. 经过步骤3的调整后， nodeAn-是满足题目要求的节点顺序， 只要把 nodeArray中的节点依
* 次重连起来即可， 整个过程结束。
*
* @author 雪瞳
*
*/
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value=data;
}
}
public class ListPart {
private Node current;//当前节点
private int nodeLength = 0 ;//链表长度
private Node nodeArray[] = null;//链表数组
private int i = 0;//循环变量
private int currentValue = 0;//节点当前值
public Node listPart(Node head,int privot) {
if(head == null) {
return head;
}
//获取链表长度
current = head;
while(current != null) {
nodeLength++;
current = current.next;
}
//将链表内容写入数组
nodeArray = new Node[nodeLength];
current = head;
while(i<nodeLength) {
nodeArray[i]=current;
i++;
current=current.next;
}
//排序
int small = -1;
int big = nodeArray.length;
int index = 0 ;
while(index != big) {
currentValue =nodeArray[index].value;
if(currentValue < privot) {
swapElements(nodeArray, ++small, index++);
}else if(currentValue > privot) {
swapElements(nodeArray, --big, index);
}else {
index++;
}
}
//重新连接链表
for(i=1;i != nodeLength;i++) {
nodeArray[i-1].next=nodeArray[i];
}
nodeArray[nodeLength-1].next=null;
head = nodeArray[0];
return head;
}
//数值交换函数
public void swapElements(Node nodeArray[], int a,int b) {
Node tranElements = null;
tranElements = nodeArray[b];
nodeArray[b] = nodeArray[a];
nodeArray[a] = tranElements;
}
}
import java.util.Random;
import java.util.Scanner;
public class TestListPart {
public static void main(String[] args) {
ListPart list = new ListPart();
TestListPart test = new TestListPart();
//获取初始信息
Random rand = new Random();
Scanner sc = new Scanner(System.in);
System.out.println("请输入链表长度");
int K = sc.nextInt();
System.out.println("请输入位置元素值");
int privot = sc.nextInt();
//随机生成链表
Node nodes[]=new Node[K];
for(int i=0;i<nodes.length;i++) {
nodes[i]=new Node(rand.nextInt(20)+1);
}
for(int i =0;i<nodes.length-1;i++) {
nodes[i].next=nodes[i+1];
}
Node head = nodes[0];
//test
test.showNode(head);
Node partNode = list.listPart(head, privot);
test.showNode(partNode);
}
public void showNode(Node head) {
System.out.println("链表内的元素如下所示...");
while(head != null) {
System.out.print(head.value+" ");
head = head.next;
}
System.out.println();
}
}
* 运行结果
