题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
代码：
方法1：
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def deleteDuplication(pHead):
if not pHead or not pHead.next:
return pHead
head=ListNode(-1)
head.next=pHead
pre=head # 指向已经确定的非重复节点
cur=pHead #工作指针
while(cur):
if cur.next and cur.next.val == cur.val:#判断是否是重复序列
while(cur.next and cur.next.val==cur.val):#cur指向重负序列的最后一个节点
cur=cur.next
pre.next=cur.next #pre的next每次都初始化指向每个单元的第一个节点，假设不重复的节点以及重复的序列都为一个单元
cur=cur.next
else: #处理已经确定不重复的节点
pre.next=cur
pre=cur
cur=cur.next
return head.next
def print_list(root):
while root != None:
print(root.val, end="->")
root = root.next
if __name__ == "__main__":
a = [2,1,1,5,5,4,2,2,2,2]
head = ListNode(a[0])
cur = head
for i in range(1, len(a)):
tmp = ListNode(a[i])
cur.next = tmp
cur = cur.next
print_list(deleteDuplication(head))
方法2(自己的方法，做的太繁琐了)：
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def deleteDuplication(pHead):
if not pHead or not pHead.next:
return pHead
head=ListNode(-1)
head.next=pHead
pre=head
cur=pHead
while(cur):
if cur.next and cur.next.val == cur.val:
while(cur.next and cur.next.val==cur.val): #指向序列的最后一个节点
cur=cur.next
if cur.next:
tmp=cur.next
if tmp.next and tmp.val==tmp.next.val:#判断后面是否是重复序列
cur=tmp
else: #若不是
pre.next=tmp
pre=tmp
cur=tmp.next
else: #若遍历到结尾
pre.next=None
break
else: #若确定当前节点非重复序列中的节点
pre.next=cur
pre=cur
cur=cur.next
return head.next
def print_list(root):
while root != None:
print(root.val, end="->")
root = root.next
if __name__ == "__main__":
a = [1,1,2,1,1,3,4,4,4,5,5,]
head = ListNode(a[0])
cur = head
for i in range(1, len(a)):
tmp = ListNode(a[i])
cur.next = tmp
cur = cur.next
print_list(deleteDuplication(head))
感想
这题看似简单，实则做起来太繁琐了，自己定义一个头结点可以将原链表的头节点当做普通节点处理
网友评论