面试题目集锦--链表

      前段时间一直在忙着找工作，在面试中也遇到了大量的算法题目。当中。问的比較多的是二叉树和链表之类的题目。在这里。我就把前段时间写的链表面试题贴出来，当然，由于题目非常多。我仅仅是在这里贴出它的类构造，不贴出实现的代码，须要的朋友能够去这里下载（免积分）：

http://download.csdn.net/detail/dlutbrucezhang/8062413

      假设由于其它别的原因下载不下来的话，留下你的邮箱。我会给你传一份。

      好吧，以下贴出链表算法类：

template <typename T>
class dutNode
{
public :
	T data;
	dutNode<T>* next;

	dutNode() : data(T()), next(NULL)	{}
	dutNode(const T& _data) : data(_data)	{}
	dutNode(const T& _data, dutNode<T>* _next) : data(_data), next(_next)	{}
};

template <typename T>
class dutLinkList
{
private :
	int count;
	dutNode<T>* pHead;

protected:		/*包裹函数*/
	dutNode<T>*	dutRecursionReverseList(dutNode<T>*);
	void		dutReversePrintList(dutNode<T>*);
	void		dutQuickSortByPointer(dutNode<T>* &, dutNode<T>* &);
	dutNode<T>* 	dutReverseOddAndEven(dutNode<T>*);
	dutNode<T>* 	dutRecursionMergeSortedList(dutNode<T>*, dutNode<T>*);
	dutNode<T>* 	dutNotRecursionMergeSortedList(dutNode<T>*, dutNode<T>*);
	dutNode<T>* 	dutFindBackwardsK(dutNode<T>*, int);
	dutNode<T>* 	dutFindMiddleElement(dutNode<T>*);
	bool		dutHasCircle(dutLinkList<T>& ,dutNode<T>* &);

	void		dutSwapData(T&, T&);

public:
	dutLinkList();
	~dutLinkList();

	/*normal operation*/
	void		dutPrintList() const;

	bool		dutIsEmpty() const;
	int		dutGetCount() const;

	int		dutAddToListByArray(const T*, int);
	int		dutAddToHead(const T&);
	int		dutAddToTail(const T&);
	int		dutAddNodeToHead(dutNode<T>*);
	int		dutAddNodeToTail(dutNode<T>*);
	int		dutAddNodeAfterData(dutNode<T>*, T);

	void		dutRemoveFirst();
	void		dutRemoveTail();
	void		dutRemoveAll();
	void		dutRemoveData(const T&);

	/*algotithm*/
	bool		dutFindNodeByData(const T&) const;	/*链表中是否存在给定值*/
	void		dutNotRecursionReverseList();		/*非递归翻转单链表*/
	void		dutRecursionReverseList();			/*递归翻转单链表*/
	void		dutReversePrintList();				/*倒序打印单链表*/
	void		dutSelectSortByData();				/*通过交换数据对单链表运行选择排序*/
	void		dutInsertSortByPointer();			/*通过交换指针对单链表运行插入排序*/
	void		dutQuickSortByPointer();			/*通过交换指针对单链表运行高速排序*/
	void		dutMergeList(dutLinkList<T>&);		/*合并单链表*/
	void		dutNotRecursionMergeSortedList(dutLinkList<T>&);	/*非递归合并有序单链表*/
	void		dutRecursionMergeSortedList(dutLinkList<T>&);		/*递归合并有序单链表*/
	void		dutReverseOddAndEven();								/*翻转链表中奇数和偶数序号节点*/
	void		dutSplitListMakeOddSeqBeforeEvenSeq();				/*切割单链表使得奇数序号位于偶数序号之前*/
	void		dutSplitListMakeOddDataBeforeEvenData();			/*切割单链表使得奇数数据位于偶数数据之前*/
	void		dutFindBackwardsK(int);								/*输出倒数第K个节点*/
	void		dutFindMiddleElement();								/*输出中间节点*/
	bool		dutHasCircle();										/*链表中是否存在环*/
	bool		dutListIntersect(dutLinkList<T>&);					/*链表是否相交*/
	bool		dutListHasCircleAndIntersect(dutLinkList<T>&);		/*链表是否有环且相交*/
	void		dutFindLoopPort();									/*输出链表环的入口*/
	void		dutFindTheFirstIntersectNode(dutLinkList<T>&);		/*输出相交链表的第一个相交节点*/
};