第二章的内容主要是关于链表的一些问题。

基础代码：

class  LinkNode{public:	int linknum;	LinkNode *next;	int isvisit;protected:private:};extern void printlinkedlist(LinkNode* head);extern LinkNode* createlinkedlist();extern LinkNode* addfirst(LinkNode* ln,LinkNode* head);extern LinkNode* addlast (LinkNode* ln,LinkNode* head);extern LinkNode* remove  (LinkNode* ln,LinkNode* head);extern LinkNode* addloop (LinkNode* ln,LinkNode* head);extern LinkNode* removeduplicate1(LinkNode* head);extern LinkNode* removeduplicate2(LinkNode* head);extern LinkNode* findlastnthnode(LinkNode* head,int n);extern LinkNode* add(LinkNode* h1,LinkNode* h2);extern LinkNode* deletemiddle(LinkNode* head,int linknum);extern LinkNode* backbeginloop(LinkNode* head);

 

LinkNode* createlinkedlist(){	LinkNode *head;	head = new LinkNode();	head->next = NULL;	return head;}LinkNode* addfirst(LinkNode* ln,LinkNode* head){	ln->next = head->next;	head->next = ln;	return head;}LinkNode* addlast (LinkNode* ln,LinkNode* head){	LinkNode* iterator;	iterator = head;	while (iterator->next != NULL)	{		iterator = iterator->next;	}	ln->next = iterator->next;	iterator->next = ln;	return head;}LinkNode* remove  (LinkNode* ln,LinkNode* head){	LinkNode* iterator = head;	while (iterator->next != NULL)	{		if (iterator->next->linknum == ln->linknum)			iterator->next = iterator->next->next;		iterator = iterator->next;	}	return head;}

 

LinkNode* addloop (LinkNode* ln,LinkNode* head){	LinkNode* iterator = head;	while (iterator->next != ln)	{		iterator = iterator->next;	}	LinkNode* newiterator = iterator->next;	while (iterator->next != NULL)	{		iterator = iterator->next;	}	iterator->next = newiterator;	return head;}

 

1.Wirte code to remove duplicates from an unsorted linked list。How would you solve this problem if a temporary buffer is not allowed？

我的思路：移除链表中重复的元素，按照第一张数组中的思路。一种利用hashtable标记元素是否已经存在，若存在则删除。另外一种思路不利用额外的存储空间的方法利用双重循环，一个指针检查一个节点时候，另外一个指针检查其他所有的元素，相同则删除。

（1）

LinkNode* removeduplicate1(LinkNode* head){	int array[26] = {0};	LinkNode* iterator = head;	while (iterator->next != NULL)	{		array[iterator->next->linknum-1]++;		if (array[iterator->next->linknum-1] > 1)			iterator->next = iterator->next->next;		else		    iterator = iterator->next;	}	return head;}

 

（2）

LinkNode* removeduplicate2(LinkNode* head){	LinkNode* tmphead;	tmphead = head->next;	while (tmphead != NULL)	{		remove(tmphead,tmphead);		tmphead = tmphead->next;	}	return head;}

 书中的一些解决方案：

 其实很类似，只是在第二种方法的时候，它的方案是外层循环1~tail，然后内层循环head~外层循环位置。

2.Implement an algorithm to find the nth to last element of a single linked list.

由于这个题目之前某次实习面试的时候被问到了，我当时不知道如何得到这个问题，当时给出的思路是遍历至链表的尾部，然后从尾部向前计数。当然这种思路比较蠢...

回来之后求助于网络，了解到利用两个指针一次便利即可完成此操作。

LinkNode* findlastnthnode(LinkNode* head,int n){	int count = 0;	LinkNode* iterator = head->next;	LinkNode* niterator = head->next;	while(iterator != NULL)	{		iterator = iterator->next;		if (count >= n)		{			niterator = niterator -> next;		}		count++;	}	return niterator;}

 书中的一些解决方案：

 

3.Implement an algorithm to delete a node in the middle of a single linked list given only access to that node.For example:

   Input:the node 'c' from the linked list a->b->c->d->e

   Result:nothing is returned,but the new linked list looks like a->b->d->e

这个题目我其实没有怎么理解，只有那个节点的访问权又是何意。in the middle of我理解成了中间的一个，所以我的代码是判断是否是这个字符，如果是则检查是否是中间的一个，如果是，则删除。

LinkNode* deletemiddle(LinkNode* head,int linknum){	LinkNode* iterator = head;	int prevcount = 0;	int nextcount = 0;	while (iterator->next->linknum != NULL)	{		prevcount++;		if (iterator->next->linknum == linknum)		{			nextcount = 0;			LinkNode* newiterator = iterator;			while (newiterator->next != NULL)			{				nextcount++;				newiterator = newiterator->next;			}			if (prevcount == nextcount)			{				iterator->next = iterator->next->next;				break;			}		}		iterator = iterator->next;	}	return head;}

  书中的一些解决方案：

 我不太确定书中的描述：

The Solution to this is to simply copy the data from the next node into this node and then delete the next node.

NOTE:This problem can not be solved if the node to be deleted is the last node in the linked list.???这里的描述不是很明白。

4.You have two numbers represented by a linked list,where each node contains a single digit.The digits are stored in reverse order,such that the 1's digit is at the head of the list.Write a function that adds the two numbers and returns the sum as a linked list.For example:

    input:3->1->5+5->9->2

    output:8->0->8

简单的加法运算。首先可以每位进行相加，如果超过了10，则进位。若是最后一个元素超过10，则需要开辟新的节点。

 

LinkNode* add(LinkNode* h1,LinkNode* h2){	LinkNode* it1 = h1->next;	LinkNode* it2 = h2->next;	int back = 0;	LinkNode* newhead = new LinkNode();	while(it1 != NULL || it2 != NULL)	{		int num = back;		back = 0;		if (it1 != NULL)		{			num += it1->linknum;			it1 = it1->next;		}		if (it2 != NULL)		{			num += it2->linknum;			it2 = it2->next;		}		if (num >= 10)		{			num -= 10;			back ++;		}		LinkNode* ln = new LinkNode();		ln->linknum = num;		addlast(ln,newhead);	}	if (back != 0)	{		LinkNode* last = new LinkNode();		last->linknum = back;		addlast(last,newhead);	}	return newhead;}

 书中的一些解决方案：

 整体思路类似，只是书中的参考利用递归计算。

　　5.Given a circular linked list,implement an algorithm which returns node at the beginning of the loop.

    　　Definition:

    　　Circular linked list:A linked list in which a node's next pointer points to an eariler node,so as to make a loop in the linked list.

    　　For example:

    　　input:a->b->c->d->e->c

    　　output:c

 这个题目看起来十分容易，但是我写起来的时候却想不起来解决方案。因为遍历这个链表根本不会有结束的条件，死循环。我执行程序的时候发现的这个问题。

后来只有改变链表内部节点的结构，添加一个标志位，如果访问过则标记，这样就容易找到开始循环的地方。

//broken the linkedlist node,maybe I can use an array or vector?LinkNode* backbeginloop(LinkNode* head){	LinkNode* iterator = head->next;	while (iterator->isvisit == 0)	{		iterator->isvisit = 1;		iterator = iterator->next;	}	return iterator;}

 书中的解决方案：

 这个题目的思考方式我觉得挺新颖的。可以这么理解，比如一个操场上两个人从共同的起点一起跑步，一个人的速度刚好是另外一个人速度的两倍，所以他们第二次必定相遇在起点的地方。这样就存在了一个结束条件。

但是这里链表的开始不能保证是起点，也就是说慢速的那个人到达链表循环的起点时候，速度快的那个人已经超过了速度慢的人k距离这么远（k为链表起点至循环起点的距离）。所以考虑不同起点的速度不同的两个人的相遇的情况...这其实是一个数据问题了，像我这种数学不是很给力的怎么也得列一个方程。 (2*speed*t + k )%n = speed*t %n

这里每次前进1，所以速度为1，则（2*t+k）%n = t%n，可以得到这个第一个t的值为n-k，所以第一次相遇在n-k的地方。

所以相遇的地方再前进k步就到达了循环的起点。然后链表的起点至循环的起点距离刚刚也是k，所以这里又是一个结束的条件。

LinkedListNode FindBeginning(LinkedListNode head) {    LinkedListNode n1 = head;    LinkedListNode n2 = head;//step1 meeting before k at beginning loop    while(n2.next != null) {        n1 = n1.next;        n2 = n2.next.next;        if ( n1 == n2)            break;    }    if(n2.next == null) {        return null;    }    n1 = head;//step 2,meeting at the beginning loop    while(n1 != n2) {        n1 = n1.next;        n2 = n2.next;     }     return n2;}