Cracking the coding interview--Q2.3

December 15, 2012
作者:Hawstein
出处:http://hawstein.com/posts/2.3.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

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

译文:

实现一个算法来删除单链表中间的一个结点,只给出指向那个结点的指针。

例子:

输入:指向链表a->b->c->d->e中结点c的指针

结果:不需要返回什么,得到一个新链表:a->b->d->e

解答

这个问题的关键是你只有一个指向要删除结点的指针,如果直接删除它,这条链表就断了。 但你又没办法得到该结点之前结点的指针,是的,它连头结点也不提供。在这种情况下, 你只能另觅他径。重新审视一下这个问题,我们只能获得从c结点开始后的指针, 如果让你删除c结点后的某个结点,那肯定是没问题的。比如删除结点d,那只需要把c 的next指针指向e,然后delete d就ok了。好的,如果我们就删除结点d,我们将得到 a->b->c->e,和目标链表只差了一个结点。怎么办呢?把d的数据给c! 结点结构都是一样的,删除谁都一样,最关键的是结点中的数据,只要我们留下的是数据 a->b->d->e就OK了。

思路已经有了,直接写代码?等等,写代码之前,让我们再简单分析一 下可能出现的各种情况(当然包括边界情况)。如果c指向链表的:1.头结点;2.中间结点。 3.尾结点。4.为空。情况1,2属于正常情况,直接将d的数据给c,c的next指针指向d 的next指向所指结点,删除d就OK。情况4为空,直接返回。情况3比较特殊,如果c 指向尾结点,一般会认为直接删除c就ok了,反正c后面也没有结点了,不用担心链表断开。 可是真的是这样吗?代码告诉我们,直接删除c,指向c的那个结点(比如说b)的next指针 并不会为空。也就是说,如果你打印这个链表,它还是会打印出和原来链表长度一样的链表, 而且最后一个元素为0!

关于这一点,原书CTCI中是这么讲的,这正是面试官希望你指出来的。然后, 你可以做一些特殊处理,比如当c是尾结点时,将它的数据设置为一些特殊字符, 这样在打印时就可以不打印它。当然也可以直接不处理这种情况,原书里的代码就是这么做 的。这里,也直接不处理这种情况。代码如下:

bool remove(node *c){
	if(c==NULL || c->next==NULL) return false;
	node *q = c->next;
	c->data = q->data;
	c->next = q->next;
	delete q;
	return true;
}

完整代码如下:

#include <iostream>
using namespace std;

typedef struct node{
	int data;
	node *next;
}node;

node* init(int a[], int n){
	node *head, *p;
	for(int i=0; i<n; ++i){
		node *nd = new node();
		nd->data = a[i];
		if(i==0){
			head = p = nd;
			continue;
		}
		p->next = nd;
		p = nd;
	}
	return head;
}

bool remove(node *c){
	if(c==NULL || c->next==NULL) return false;
	// if(c->next==NULL){//c为最后一个元素时直接删除,不行,最后还是会打印出一个为0的结点,需要特殊处理
	//     delete c;
	//     return;
	// }
	node *q = c->next;
	c->data = q->data;
	c->next = q->next;
	delete q;
	return true;
}
void print(node *head){
	while(head){
		cout<<head->data<<" ";
		head = head->next;
	}
	cout<<endl;
}

int main(){
	int n = 10;
	int a[] = {
		9, 2, 1, 3, 5, 6, 2, 6, 3, 1 
	};
	node *head = init(a, n);
	int cc = 3;
	node *c = head;
	for(int i=1; i<cc; ++i) c = c->next;
	print(head);
	if(remove(c))
		print(head);
	else
		cout<<"failure"<<endl;
	return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview