【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“删除无序单链表中值重复出现的节点”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
给定一个无序单链表的头节点 head,删除其中值重复出现的节点。
例如:1->2->3->3->4->4->2->1->NULL,删除值重复的节点之后为1->2->3->4->NULL。
请按以下要求实现两种方法:
方法一:如果链表长度为 N,时间复杂度达到 O(N)。
方法二:额外空间复杂度为O(1)。
【思路】:
解法一:使用哈希表。
解法二:类似选择排序方法的循环遍历。
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:list_removeRep
3 *作者:
4 *摘要:移除链表中值出现的重复节点
5 */
6
7 #include <iostream>
8 #include <hash_set>
9
10 using namespace std;
11
12 using namespace __gnu_cxx;
13
14 class Node
15 {
16 public:
17 Node(int data)
18 {
19 value = data;
20 next = NULL;
21 }
22 public:
23 int value;
24 Node *next;
25 };
26
27 void removeRep1(Node *head)
28 {
29 if(NULL == head)
30 return ;
31 hash_set<int> set;
32 Node *pre = head;
33 Node *cur = head->next;
34 Node *ptr = NULL;
35 set.insert(head->value);
36 while(NULL != cur)
37 {
38 if(set.find(cur->value) != set.end())
39 {
40 pre->next = cur->next;
41 delete cur;
42 }
43 else
44 {
45 set.insert(cur->value);
46 pre = cur;
47 }
48 cur = pre->next;
49 }
50 return ;
51 }
52
53 void removeRep2(Node *head)
54 {
55 Node *cur = head;
56 Node *pre = NULL;
57 Node *next = NULL;
58 while(NULL != cur)
59 {
60 pre = cur;
61 next = cur->next;
62 while(NULL != next)
63 {
64 if(cur->value == next->value)
65 {
66 pre->next = next->next;
67 delete next;
68 }
69 else
70 {
71 pre = next;
72 }
73 next = pre->next;
74 }
75 cur = cur->next;
76 }
77 }
78
79 void printList(Node *head)
80 {
81 while(NULL != head)
82 {
83 cout << head->value << " ";
84 head = head->next;
85 }
86 cout << endl;
87 }
88
89 int main()
90 {
91 Node *head = NULL;
92 Node *ptr = NULL;
93
94 for(int i =1;i<7;i++)//构造链表
95 {
96 if(NULL == head)
97 {
98 head = new Node(i);
99 ptr = head;
100 continue;
101 }
102 ptr->next = new Node(i);
103 ptr = ptr->next;
104 ptr->next = new Node(i);
105 ptr = ptr->next;
106 }
107 cout << "before remove:" << endl;
108 printList(head);
109 cout << "after remove:" << endl;
110 // removeRep1(head);
111 removeRep2(head);
112 printList(head);
113 return 0;
114 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5418731.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/232279
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!