欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

将单链表按值划分成左小中间等右边大的形式

程序员文章站 2022-05-06 11:33:07
...

题目:

给定一个单项链表的头结点dead,节点的值类型都是整型,在给定一个数pivot。实现一个调整链表的函数,将链表调整成左部分值都是小于pivot,中间部分都是等于值pivot,右边部分都是大于值pivot的部分。
等同于荷兰国旗问题

	public static Node partition1(Node head, int num) {
		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, num);
		for (i = 0; i != nodeArr.length; i++) {
			nodeArr[i - 1].next = nodeArr[i];
		}
		nodeArr[i - 1].next = null;
		return nodeArr[0];
	}
	
	private static void arrPartition(Node[] nodeArr, int num) {
		int less = 0;
		int more = nodeArr.length;
		int cur = 0;
		while (cur != more) {
			if (nodeArr[cur].value < num) {
				swap(nodeArr, ++less, cur++);
			} else if (nodeArr[cur].value > num) {
				swap(nodeArr, --more, cur);
			} else {
				cur++;
			}
		}
	}

	public static void swap(Node[] arr, int i, int j) {
		Node temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

进阶:

链表长度为N 时间复杂度达到o(N) 额外空间复杂度达到o(1)
我们要知道荷兰国旗问题是不能保证稳定性的
设置三个节点变量less equal more 为空 然后分别给这三个区域设置end 先是遍历一遍链表 找到第一个小于的节点 第一个等于的节点 第一个大于的节点 不存在的话还是空
在遍历一遍,发现小于num的(不是less),然后挂到less区域的end上面,发现等于num的但是不能是equal,然后挂到equal区域的end上面 大于同样如此
最后less区域的尾部和equal区域的头部相连,equal区域的尾部和more区域的头部相连
将单链表按值划分成左小中间等右边大的形式

	public static Node partition2(Node head, int num) {
		Node SH = null;  //小于部分头
		Node ST = null;  //小于部分尾
		Node EH = null;  //等于部分头
		Node ET = null;  //等于部分尾
		Node MH = null;  //大于部分头
		Node MT = null;  //大于部分尾
		Node next = null; //保存下一个节点
		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < num) {     // 发货 
				if(SH == null) {
					SH = head;
					ST = head;
				} else {
					ST.next = head;
					ST = head;
				}
			} else if (head.value == num) {
				if (EH == null) {
					EH = head;
					ET = head;
				} else {
					ET.next = head;
					ET = head;
				}
			} else {
				if (MH == null) {
					MH = head;
					MT = head;
				} else {
					MT.next = head;
					MT = head;
				}
			}
		}
		if (ST != null) {                               // 装货  --  要考虑某个部分为空的情况
			ST.next = EH;
			ET = ET == null ? ST : ET;
		}
		if (ET != null) {
			ET.next = MT;
		}
		return SH != null ? SH : EH != null ? EH : MH;   //返回
	}