Description: Given a sorted linked list, delete all duplicates such that each element appear only once.
Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list/
思路: 我们会如何删除list的重复元素呢?很简单,我们会记录前一个元素的值,然后与当前元素进行比较,相同则略过,不同则加入要返回的list中。。那么我们只需要将对list的操作换成链表就可以了,但特别值得注意的是,我们如果结尾两个元素相同,我们将倒数第二个元素加入新的链表,一定要将node.next = None,否则就会将后面的全部加入,是错的。
a = [1,1,2,3,3] pre = a[0] b = [] b.append(pre) for i in a[1:]: if i != pre: b.append(i) pre = i print(b)
换成linkedlist:
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return head if not head.next: return head rhead = head r = rhead p = head.next pre = head.val while p: # print(pre) if p.val != pre: pre = p.val r.next = p r = r.next p = p.next r.next = None return rhead
如果直接在原链表上进行删除,不添加新的链表,时间会增加,空间会稍减少:
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return head if not head.next: return head pre = head # moving node of the returned linkedlist cur = head.next while cur: if cur.val == pre.val: pre.next = cur.next #remove current node else: pre.next = cur #join current node pre = pre.next #point to the next cur = cur.next return head
日期: 2020-11-17 晨跑很舒服,是元气满满的一天,不要焦虑,要充实