【CareerCup】 Linked Lists—Q2.1

전재 출처 를 밝 혀 주 십시오:http://blog.csdn.net/ns_code/article/details/21644083
   
    제목:
    Write code to remove duplicates from an unsorted linked list.
    FOLLOW UP
    How would you solve this problem if a temporary buffer is not allowed?
    번역:
    정렬 되 지 않 은 링크 에서 중복 되 는 항목 을 제거 하 는 프로그램 을 작성 합 니 다.
    또한 임시 캐 시 를 사용 할 수 없다 면 이 문 제 를 어떻게 해결 하 시 겠 습 니까?
    생각:
    링크 는 정렬 되 지 않 았 습 니 다. 만약 에 링크 의 요소 가 모두 문자 라면 분명 합 니 다. 앞의 문자열 에서 중복 문 자 를 판단 하거나 제거 하 는 사상 과 마찬가지 로 가장 좋 은 방법 은 해시 사상 으로 bool 배열 을 열 어 매 핑 하 는 것 입 니 다. 배열 에서 해당 하 는 위치 에 있 는 요소 값 이 true 일 때 이 위치 에 다시 매 핑 되면 링크 에 해당 하 는 문 자 를 삭제 합 니 다.시간 복잡 도 는 O (n) 이다.
    그러나 만약 에 링크 의 요소 가 문자 가 아니 라 정수 라면 정수 가 플러스 와 마이너스 가 있 거나 가장 큰 숫자 가 크다 면 해시 의 사상 을 사용 하면 안 된다. 마이너스 가 있 을 때 해시 배열 이 경 계 를 넘 을 수 있다. 링크 에서 요소 의 최대 치 는 매우 큰 꽃 이 고 큰 배열 공간 을 열 어야 한다.그리고 배열 사이 의 많은 공간 을 낭비 할 수도 있다.
    제자리 에서 삭제 하려 면?정렬 사용 하기?예 를 들 어 빠 른 배열, 병합 정렬, 정렬 등 을 보면 어떻게 보면 시간 복잡 도 O (nlogn) 를 볼 수 있 습 니까? 그러나 우 리 는 링크 에 있어 요소 가 있 는 위 치 를 찾 을 때마다 전체 링크 를 옮 겨 다 녀 야 한 다 는 것 을 알 고 있 습 니 다. 이 몇 가지 효율 적 인 정렬 알고리즘 은 모든 단계 의 정렬 작업 에 대응 하 는 요소 의 위 치 를 알 아야 하기 때문에 링크 에 대해 이 몇 가지 정렬 속 도 를 하 는 것 이 느 릴 것 입 니 다.
    그 러 고 보 니 제자리 에서 삭제 하려 면 시간 복잡 도가 O (n * n) 인 방법 만 사용 할 수 있 습 니 다. 즉, 두 개의 지침 으로 지침 A 는 먼저 첫 번 째 요 소 를 가리 키 고 지침 B 는 뒤의 요 소 를 옮 겨 다 니 며 A 가 가리 키 는 요소 와 비교 하고 A 가 가리 키 는 요소 와 같은 것 을 만나면 삭제 한 다음 에 지침 A 를 옮 긴 다음 에 똑 같은 비 교 를 합 니 다.포인터 A 가 마지막 위치 로 이동 할 때 까지
    구현 코드:    

/*
删除链表中重复的元素
*/
void remove(PNODE pHead)
{
	if(!pHead)
		return ;
	PNODE p1;
	PNODE p2;
	PNODE p2_prior;  //指向p2前面的一个元素
	for(p1 = pHead->pNext ; p1 ; p1 = p1->pNext)
	{
		p2 = p1->pNext;
		p2_prior = p1;
		while(p2)
		{
			//如果当前元素需要删除，则在删除该元素后，p2需要跳过该元素
			if(p1->data == p2->data)
			{
				p2_prior->pNext = p2->pNext;
				free(p2);
				p2 = p2_prior->pNext;
			}
			else
			{	//如果当前元素不需要删除，则p2直接向后移动
				p2_prior = p2;
				p2 = p2->pNext;
			}
		}
	}
}

    전체 코드 (이전에 쓴 단일 링크 로 직접 조작):    

/***************************************************
题目描述：
不用额外的辅助空间，删除一个未排序的链表中重复的元素
Date:2014-03-20
****************************************************/


/**************************************************************************************************************
以下为操作链表的算法，该链表为单链表。
链表以头指针为索引，头指针指向头节点，头节点指向首节点，以此类推，直到尾节点。
头节点中不存放数据，只存放指向首节点的指针，
设置头节点的目的是为了方便对链表的操作，如果不设置头节点，而是直接由头指针指向首节点，
这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同，便要作为一种特殊情况来分析
**************************************************************************************************************/

#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

PNODE create_list();       
void traverse_list(PNODE);
bool is_empty(PNODE);     
int length_list(PNODE); 
void sort_list(PNODE);    
bool insert_list(PNODE,int,int);
bool delete_list(PNODE,int,int *);
void clear_list(PNODE);
void remove(PNODE);

int main(void)
{
	int len;
	PNODE pHead = NULL;

	//创建链表并遍历输出
 	pHead = create_list();
	traverse_list(pHead);

	//求链表长度，并输出
	len = length_list(pHead);
	if(!is_empty(pHead))
		printf("the length of the list is:%d
",len);
	
	remove(pHead);
	printf("After removing duplicate, ");
	traverse_list(pHead);
	
	//清空链表，遍历输出（无数据输出）
	clear_list(pHead);
	printf("After cleared,");
	traverse_list(pHead);	
	return 0;
}

/*
  创建一个链表,并返回头指针
*/
PNODE create_list()
{
	int val;
	PNODE pHead =(PNODE)malloc(sizeof(NODE));
	PNODE pCurrent = pHead;
	pCurrent->pNext = NULL;
	if(NULL == pHead)
	{
		printf("pHead malloc failed!");
		exit(-1);
	}
	printf("Input first data(q to quit):");
	while(scanf("%d",&val)==1)
	{
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL == pNew)
		{
			printf("pNew malloc failed!");
			exit(-1);
		}
		pNew->data = val;
		pCurrent->pNext = pNew;
		pNew->pNext = NULL;
		pCurrent = pNew;
		printf("Input next data(q to quit):");
	}

	return pHead;	
}

/*
遍历链表
*/
void traverse_list(PNODE pHead)
{
	PNODE pCurrent = pHead->pNext;
	printf("now dataes in the list are:
");
	while(pCurrent != NULL)
	{	
		printf("%d ",pCurrent->data);
		pCurrent = pCurrent->pNext;
	}
	printf("
");
	return ;
}

/*
判断链表是否为空
*/
bool is_empty(PNODE pNode)
{
	if(NULL == pNode->pNext)
		return true;
	else 
		return false;
}

/*
求链表长度，即节点总数（不计入头节点）
*/
int length_list(PNODE pNode)
{
	int count = 0;
	PNODE pCurrent = pNode->pNext;
	while(pCurrent != NULL)
	{
		count++;
		pCurrent = pCurrent->pNext;		
	}

	return count;
}

/*
选择法对链表排序
*/
void sort_list(PNODE pHead)
{
	PNODE p,q;
	int temp;
	for(p=pHead->pNext;p!=NULL;p=p->pNext)
	    for(q=p->pNext;q!=NULL;q=q->pNext)
		{
		   if(p->data>q->data)
	              {
			 temp = p->data;
			 p->data = q->data;
			 q->data = temp;
		      }
		}

	return ;
}

/*
在第pos个节点的后面插入一个新的节点，该节点中的数据为val
*/
bool insert_list(PNODE pHead,int pos,int val)
{
	int i = 0;
	PNODE p = pHead;

        //i为0时，p指向第0个节点（这里指没有实际数据的头节点，不计入链表节点总数），
	//i为1时，p指向第1个节点，i为几，p就指向第几个节点
	while(p!=NULL && i<pos)
	{
	   p = p->pNext;
	   i++;
	}

	//当pos的值大于链表长度时，便会出现这种情况
	if(i>pos || p==NULL)
	   return false;

	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew)
	{
	   printf("pNew malloc failed!");
	   exit(-1);
	}
	pNew->data = val;
	pNew->pNext = p->pNext;
	p->pNext = pNew;

	return true;
}

/*
删除第pos个节点，并将删除的数据保存在pData指针所指向的位置
*/
bool delete_list(PNODE pHead,int pos,int *pData)
{
	int i = 0;
	PNODE p = pHead;

	//p最终指向第pos个节点前面的节点
	//如果下面两句分别改为while(p!=NULL && i<pos)和if(i>pos || p==NULL)，则p最终指向第pos个节点，
	//这样因为得不到第pos个节点前面的那个节点，因此无法将pos前后两个节点连结起来
	while(p->pNext!=NULL && i<pos-1)
	{
	   p = p->pNext;
	   i++;
	}

	//当pos的值大于链表长度时，便会出现这种情况
	if(i>pos-1 || p->pNext==NULL)
	   return false;

	PNODE q = p->pNext;
	*pData = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}

/*
清空链表，即使链表只剩下头节点（头节点中没有数据）
*/
void clear_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	PNODE r = NULL;
	while(p != NULL)
	{
	   r = p->pNext;
	   free(p);
	   p = r;
	}
	pHead->pNext = NULL;
	return ;
}

/*
删除链表中重复的元素
*/
void remove(PNODE pHead)
{
	if(!pHead)
		return ;
	PNODE p1;
	PNODE p2;
	PNODE p2_prior;  //指向p2前面的一个元素
	for(p1 = pHead->pNext ; p1 ; p1 = p1->pNext)
	{
		p2 = p1->pNext;
		p2_prior = p1;
		while(p2)
		{
			//如果当前元素需要删除，则在删除该元素后，p2需要跳过该元素
			if(p1->data == p2->data)
			{
				p2_prior->pNext = p2->pNext;
				free(p2);
				p2 = p2_prior->pNext;
			}
			else
			{	//如果当前元素不需要删除，则p2直接向后移动
				p2_prior = p2;
				p2 = p2->pNext;
			}
		}
	}
}

    테스트 결과: