[코딩인터뷰] 문제 2.4

문제 2.4

	#region Question 2.4
	/// <summary>
	/// <paramref name="pivot"/>값을 갖는 노드를 기준으로 연결 리스트를 나눠라.
	/// (<paramref name="pivot"/>보다 작은 값을 갖는 노드가 같거나 더 큰 값을 갖는 노드들보다 앞에 오도록)
	/// </summary>
	/// <typeparam name="T"><code>LinkedListNode</code>의 Generic Type</typeparam>
	/// <param name="head">리스트의 시작지점</param>
	/// <param name="pivot">기준값</param>
	/// <returns>새로운 head</returns>
	public static LinkedListNode<int> Q4_Partition(LinkedListNode<int> head, int pivot)
	{
	if (head == null) return head;
	//Tail 계산
	var tail = head;
	int count = 1;
	while (tail.Next != null)
	{
	tail = tail.Next;
	count++;
	}
	var node = head;
	for(int index = 0; index < count; index++)
	{
	var next = node.Next;
	if(node.Data >= pivot)
	{
	tail.Next = node;
	if (node.Prev != null) node.Prev.Next = node.Next;
	if (node.Next != null) node.Next.Prev = node.Prev;
	node.Prev = tail;
	node.Next = null;
	tail = node;
	}
	node = next;
	}
	//새로운 Head
	var newHead = tail;
	while (newHead.Prev != null)
	{
	newHead = newHead.Prev;
	}
	return newHead;
	}
	#endregion

view raw Code_Q2_4.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q2_4()
	{
	const int max = 30;
	//테스트 이전 설정
	Random rand = new Random();
	var head = new LinkedListNode<int>(rand.Next(0, max), null, null);
	LinkedListNode<int> prev = head, node;
	for (int i = 1; i < max; i++)
	{
	node = new LinkedListNode<int>(rand.Next(0, max), null, null);
	node.Prev = prev;
	prev.Next = node;
	prev = node;
	}
	//코드 테스트
	int pivot = rand.Next(0, max);
	var result = LinkedList.Q4_Partition(head, pivot);
	//코드 테스트 결과 검증
	bool pass = false;
	var current = result;
	while (current != null)
	{
	if (pass)
	{
	Assert.IsTrue(current.Data >= pivot);
	}
	else
	{
	if (current.Data > pivot)
	{
	pass = true;
	}
	}
	current = current.Next;
	}
	}

view raw Test_Q2_4.cs hosted with ❤ by GitHub