将一个单向链表按照某个值划分为左边小、中间相等、右边大的形式

将一个单向链表按照某个值划分为左边小、中间相等、右边大的形式

问题重述:

给定一个单向链表的头节点,节点的类型是整形,在给定一个整数pivot,实现一个调整链表的函数,将链表划分成左边都是小于pivot的结点,中间都是等于的结点,右边都是大于的结点(调整后的结点顺序不做要求)

进阶:左中右的结点顺序与原链表中的顺序相同,并且时间复杂度达到O(N),空间复杂度达到O(1)

问题分析:

这道题的重点是排序方式,链表的排序不容易,但是数组的排序很简单,我们可以将链表添加到数组中去,然后在数组中进行排序,排完序后再变成链表就可以

对于进阶题,我们不能创建数组来解决,那么我们可以在遍历链表的过程中,将三种类型的结点划分开,然后最后将链表合并起来就是我们要的结果

解法:

普通解法:将所有的值加入到数组中,在数组中进行排序,排完序后再重新连接

进阶解法:将链表划分成三个链表,遍历链表,符合哪一个要求就加入到哪一个链表中去,最后将三个链表连接起来返回就可以

解题:

代码:
普通:
public static Node listPartition1(Node head,int pivot) {
		if(head == null) {
			return head;
		}
		Node cur = head;
		int i = 0;
		while(cur != null) {
			i++;
			cur = cur.next;
		}
		Node[] nodeArr = new Node[i];
		i = 0;
		cur = head;
		for(i = 0;i < nodeArr.length;i++) {
			nodeArr[i] = cur;
			cur = cur.next;
		}
		arrPartition(nodeArr,pivot);
		for(i = 1;i != nodeArr.length;i++) {
			nodeArr[i-1].next = nodeArr[i];
		}
		nodeArr[i-1].next = null;
		return nodeArr[0];
	}
public static void arrPartition(Node[] nodeArr, int pivot) {
		int small = -1;
		int big = nodeArr.length;
		int index = 0;
		while(index != big) {
			if(nodeArr[index].value < pivot) {
				swap(nodeArr,++small,index++);
			}else if(nodeArr[index].value == pivot) {
				index++;
			}else {
				// 这里的index不加1的原因是此时index的值是big所对应的值,需要重新比较
				swap(nodeArr,--big,index);
			}
		}
		
	}
	/**
	 * 交换结点的方法
	 * @param nodeArr
	 * @param a
	 * @param b
	 */
	public static void swap(Node[] nodeArr,int a,int b) {
		Node temp = nodeArr[a];
		nodeArr[a] = nodeArr[b];
		nodeArr[b] = temp;
	}

代码解析:这段代码重点在于排序,除了排序过程,其他过程都一目了然。排序过程使用了一部分的快排思想,对数组中的每一个元素的值和pivot进行比较,如果比该值小,那么就将当前的值和首部指针对应的数组元素进行置换,然后将当前指针前进一格(置换之后直接更新当前指针的原因是,首部指针当前对应的值一定是小于pivot的(small一开始是-1,后面每次更新的值都是小于pivot的值),并且题目不要求顺序),如果当前指针对应的值等于pivot,那么直接更新指针,如果当前指针对应的值大于pivot,将当前指针对应的值和尾部指针对应的元素进行置换,需要注意的是,置换完成之后,当前的index的大小是不确定的,我们需要再次对该值进行比较,所以index不能直接更新。

进阶
public static Node listPartition2(Node head,int pivot) {
		if(head == null) {
			return head;
		}
		// 定义三段链表分别为大链表小链表和等于链表
		Node smallHead = null;
		Node smallTail = null;
		Node equalHead = null;
		Node equalTail = null;
		Node bigHead = null;
		Node bigTail = null;
		Node next = null;
		// 对链表进行遍历
		while(head != null) {
			// 将head的下一个结点设置为null,方便加入我们的新链表中
			next = head.next;
			head.next = null;
			if(head.value < pivot) {
				// 小于则加入小链表中
				if(smallHead == null) {
					// 小链表为null,则head既为头也为尾
					smallHead = head;
					smallTail = head;
				}else {
					// 小链表不为null,则将head添加到尾部(因为题目要求按照原顺序)
					smallTail.next = head;
					smallTail = head;
				}
			}else if(head.value == pivot) {
				// 等于则加入等于链表中
				if(equalHead == null) {
					// 等于链表为null,则head既为头也为尾
					equalHead = head;
					equalTail = head;
				}else {
					// 等于链表不为null,则将head添加到尾部(因为题目要求按照原顺序)
					equalTail.next = head;
					equalTail = head;
				}
			}else {
				// 既不小于也不等于,那么就是大于
				if(bigHead == null) {
					bigHead = head;
					bigTail = head;
				}else {
					bigTail.next = head;
					bigTail = head;
				}
			}
			head = next;
		}
		// 循环完成后,我们将三个链表联结起来就可以
		if(smallTail != null) {
			smallTail.next = equalHead;
			equalTail = (equalTail == null ? smallTail : equalTail);
		}
		if(equalTail != null) {
			equalTail.next = bigHead;
		}
		return smallHead != null ? smallHead : (equalHead != null ? equalHead : bigHead);
	}

代码解析:就是定义三段链表,然后遍历原链表,将链表结点的值和pivot进行比较,按照类别加入不同的链表中,最后将三个链表联结起来,需要注意链表为null的情况

总结:

快速排序的方法:

  1. 首先确定一个基准数(pivot),这个值可以随机取,也可以取第一个值(我们一般取第一个值,如果基准值不是第一个值,我们可以把那个值和第一个值交换位置)
  2. 定义两个指针,分别指向所有值的首尾,将第一个元素保存起来,将首部指针置空
  3. 左右指针交替和基准值进行比较,先用右指针进行比较
    如果右边指针大于基准值,右边指针往左移,继续和基准值进行比较
    如果小于基准值,将右边指针对应的值移动到左边指针对应的位置,然后左指针右移,开始对左指针的值和基准值进行比较
  4. 左指针和基准值进行比较
    如果左边指针小于基准值,左边指针右移,继续和基准值进行比较
    如果大于基准值,就把左边指针对应的值移动到右边指针对应的位置,然后右指针左移,循环3、4的操作
  5. 最后等到左右指针指向同一位置的时候,将基准值加入到这个位置,此时这些数在基准值左边的元素都小于基准值,大于基准值的元素都大于基准值
  6. 最后,使用递归的方法对基准值左边元素和基准值右边元素分别进行排序
上一篇:js基础-数组


下一篇:Java 对象游离