Cracking the Coding Interview(linked list)

第二章の内容は主にチェーンテーブルに関するいくつかの問題である.
基本コード:

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つの考え方は,余分な記憶空間を利用しない方法で二重ループを利用し,1つのポインタが1つのノードを検査するとき,もう1つのポインタが他のすべての要素を検査し,同じように削除する.
(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;
}

本の中のいくつかの解決策:
実は似ていますが、第2の方法の場合、外層サイクル1~tail、次いで内層サイクルhead~外層サイクル位置がそのスキームです.
2.Implement an algorithm to find the nth to last element of a single linked list.
この問題の前にある実習面接の時に聞かれたので、私はどのようにこの問題を得るか分かりませんでした.その時、チェーン時計の尾まで遍歴して、尾から前に数えます.もちろんこの考えは愚かです...
帰ってきてからネットワークに助けを求め、2つのポインタを利用して一度に便利に操作できることを知った.

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私は中間の1つと理解しているので、私のコードはこの文字かどうかを判断し、もしそうであれば中間の1つかどうかをチェックし、もしそうであれば削除します.

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
単純な加算.まず1桁ずつ加算することができ、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;
}

本の中の解決策:
この問題の考え方は斬新だと思います.例えば、ある運動場で二人が共通の起点から一緒に走っていると、一人のスピードはちょうど別の人のスピードの2倍なので、彼らは2回目に必ず起点の場所で出会ったと理解できます.これで終了条件が存在します.
しかし、ここでチェーン時計の始まりが起点であることは保証できません.つまり、遅い人がチェーン時計の循環の起点に着いたとき、速度の速い人はすでに速度の遅い人の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;
}