[코딩인터뷰] 문제 2.7

문제 2.7

	#region Question 2.7
	/// <summary>
	/// 주어진 연결 리스트가 회문인지 검사하는 함수를 작성하라.
	/// </summary>
	/// <param name="head">리스트의 시작 노드</param>
	/// <returns>회문검사 결과</returns>
	public static bool Q7_IsPalindrome(LinkedListNode<int> head)
	{
	var fast = head;
	var slow = head;
	var stack = new System.Collections.Generic.Stack<int>();
	/*
	* 연결 리스트를 Stack에 쌓는다.
	* (처음 구현할 때는 모든 원소를 쌓았으나, 책 정답을 반영하여 절반만 쌓는다.)
	* fast와 slow 방법을 활용하여 원소 중간 지점을 체크한다.
	*/
	while (fast != null && fast.Next != null)
	{
	stack.Push(slow.Data);
	slow = slow.Next;
	fast = fast.Next.Next;
	}
	// 리스트 길이가 홀수라면, 가운데 원소는 매칭하는 원소가 자기 자신이므로 제외한다.
	if (fast != null)
	{
	slow = slow.Next;
	}
	while (slow != null)
	{
	var top = stack.Pop();
	// 값이 다르면 회문 리스트가 아니다.
	if (top != slow.Data)
	{
	return false;
	}
	slow = slow.Next;
	}
	return true;
	}
	#endregion

view raw Code_Q2_7.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q2_7()
	{
	Random rand = new Random();
	int length = rand.Next(2, 30);
	var nodes = new LinkedListNode<int>[length];
	for (var i = 0; i < length; i++)
	{
	nodes[i] = new LinkedListNode<int>(i >= length / 2 ? length - i - 1 : i, null, null);
	}
	for (var i = 0; i < length; i++)
	{
	if (i < length - 1)
	{
	nodes[i].SetNext(nodes[i + 1]);
	}
	if (i > 0)
	{
	nodes[i].SetPrevious(nodes[i - 1]);
	}
	}
	var head = nodes[0];
	Assert.IsTrue(LinkedList.Q7_IsPalindrome(head));
	nodes[length - 2].Data = 9;
	Assert.IsFalse(LinkedList.Q7_IsPalindrome(head));
	}

view raw Test_Q2_7.cs hosted with ❤ by GitHub