Created
April 2, 2019 06:11
-
-
Save imhuwq/0604837fa9a24b0c452fa8bcea4e843e to your computer and use it in GitHub Desktop.
移除单向链表中的所有重复元素
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
def __init__(self): | |
self.next = None | |
self.val = None | |
@classmethod | |
def from_list(cls, l): | |
pre = Node() | |
head = pre | |
for i in l: | |
n = Node() | |
n.val = i | |
pre.next = n | |
pre = n | |
return head.next | |
@staticmethod | |
def to_list(node): | |
if node is None: | |
return [] | |
ls = [] | |
cur = node | |
while cur is not None: | |
ls.append(cur.val) | |
cur = cur.next | |
return ls | |
def __repr__(self): | |
return "->".join(map(str, Node.to_list(self))) | |
def remove_duplicated_elements(node): | |
if node is None: | |
return None | |
pre = Node() | |
origin = pre | |
cur = node | |
nex = node.next | |
last = pre | |
delete_cur = False | |
while nex is not None: | |
if cur.val == nex.val: | |
delete_cur = True | |
nex = nex.next | |
else: | |
if not delete_cur: | |
pre.next = cur | |
pre = cur | |
cur = nex | |
nex = cur.next | |
else: | |
cur = nex | |
nex = cur.next | |
delete_cur = False | |
if not delete_cur: | |
pre.next = cur | |
else: | |
pre.next = None | |
return origin.next | |
def generate_list(len): | |
result = [] | |
for i in range(1, len + 1): | |
result.append([i]) | |
pos = 1 | |
while pos < len: | |
temp = [] | |
for s in result: | |
for i in range(s[-1], len + 1): | |
ds = s[:] | |
ds.append(i) | |
temp.append(ds) | |
result = temp | |
pos += 1 | |
return result | |
class Test: | |
@staticmethod | |
def remove_duplicate(ls): | |
vals = [] | |
for i in ls: | |
if ls.count(i) > 1: | |
continue | |
vals.append(i) | |
return vals | |
@staticmethod | |
def test(ls): | |
node = Node.from_list(ls) | |
new_node = remove_duplicated_elements(node) | |
deduplicated = Test.remove_duplicate(ls) | |
try: | |
assert deduplicated == Node.to_list(new_node) | |
except AssertionError as e: | |
print(deduplicated) | |
print(Node.to_list(new_node)) | |
raise e | |
@staticmethod | |
def run(): | |
elements_len = 6 | |
for len in range(elements_len+1): | |
lists = generate_list(len) | |
for l in lists: | |
Test.test(l) | |
if __name__ == "__main__": | |
t = Test() | |
t.run() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment