Basic Operation 增删查改
删除Delete
class Solution(object):
def removeElements(self, head, val):
dummyNode = ListNode(0)
dummyNode.next = head
prev, cur = dummyNode, head
while cur:
if cur.val == val:
prev.next = cur.next
else:
prev = cur
cur = cur.next
return dummyNode.next
class Solution(object):
def removeNthFromEnd(self, head, n):
dummyNode = ListNode(0)
dummyNode.next = head
slow = fast = dummyNode
for _ in xrange(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummyNode.next
- 很奇怪的一道题，做法也很奇怪
- 往往删除单链表的一个节点，需要有头节点或者前一个节点来绕过删除的节点，这道题只给了要删除的节点(单链表拿不到previous的节点)，只能通过节点覆盖来做。
class Solution(object):
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
- 和Remove Duplicate from Array一毛一样同样是同向双指针
class Solution(object):
def deleteDuplicates(self, head):
if not head: return head
prev = head
cur = head.next
while cur:
if cur.val == prev.val:
prev.next = cur.next
cur = cur.next
else:
prev = cur
cur = cur.next
return head
- 删除所有的duplicate，只保留distinct的元素！
- 1 找到重复的元素
- 2 用while循环删除掉所有
class Solution(object):
def deleteDuplicates(self, head):
dummyNode = ListNode(-1)
dummyNode.next = head
prev = dummyNode
cur = head
while cur:
if cur.next and cur.val == cur.next.val:
while cur.next and cur.val == cur.next.val:
cur = cur.next
prev.next = cur.next
else:
prev = cur
cur = cur.next
return dummyNode.next