Q2.1 Write code to remove duplicates from an unsorted linked list. -开发者知识库

Q2.1 Write code to remove duplicates from an unsorted linked list. -开发者知识库,第1张

Q:

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?


A:

用哈希表記錄某一值是否已經存在,下面的程序只對小於100的數有效。

1、當訪問的鏈表節點置為i時,如果此時hash[i] == false, 那么將其置true, 繼續訪問下一個節點,直到遍歷結束。

2、如果hash[i] == true, 說明已經出現過值為i的節點了,要將該節點刪除,繼續訪問下一個節點,直到遍歷結束。


如果只允許常量的空間,那么就要用兩次遍歷。需要兩個指針,第一個指針指向鏈表中某個元素, 第二個元素從第一個指針的下一個元素開始遍歷,刪除與第一個指針指向的元素值相同的節點。


#include <iostream>
using namespace std;

struct ListNode {
    int val;
	ListNode *next;
 	ListNode(int x) : val(x), next(NULL) {}
 };
 bool hash[100];
 ListNode *init(int a[], int n) {
 	ListNode *head = NULL;
 	ListNode *p = NULL;
 	for (int i = 0; i < n; i  ) {
 		ListNode *cur = new ListNode(a[i]);
 		if (i == 0) {
 			head = cur;
 			p = cur;
 		}
 		p->next = cur;
 		p = cur;
 	}
 	return head;
 }
 void removedulicate1(ListNode *head){
    if(head==NULL) return;
    ListNode *p=head;
    hash[head->val] = true;
    while(p->next){
        if(hash[p->next->val]){
            ListNode *t = p->next;
            p->next = p->next->next;
            delete t;
        }
        else{
            hash[p->next->val] = true;
            p = p->next;
        }
    }
}
 void removedulicate2(ListNode *head){
    ListNode *cur=head;
    while(cur){
        ListNode *run = cur;
        while (run->next) {
        	if (run->next->val == cur->val) {
        		ListNode *t = run->next;
        		run->next = run->next->next;
        		delete t;
        	} else {
        		run = run->next;
        	}
        }
        cur = cur->next;
    }
}

void printList(ListNode *head) {
	ListNode *p = head;
	for( ; p; p = p->next) {
		cout<<p->val<<" ";
	}
	cout<<endl;
}
int main() {
	int a[10] = {1,5,2,6,7,4,6,2,8,9};
	ListNode *head = init(a, 10);
	printList(head);
	//removedulicate1(head);
	removedulicate2(head);
	printList(head);
	return 0;
}


最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复