这里我把删除有关的放在一起讲.
Remove Linked List Elements
删除就是把要删除的节点前一个的 next 指向别的, 把它自己的 next 连上去
class Solution:
# @param {ListNode} head
# @param {integer} val
# @return {ListNode}
def removeElements(self, head, val):
head2 = ListNode(-1)
head2.next = head
pointer = head2
while pointer and pointer.next:
if pointer.next.val == val:
pointer.next = pointer.next.next
else: pointer = pointer.next
return head2.next
Remove Duplicates from Sorted List
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
if not head or not head.next: return head
pointer = head
while pointer is not None and pointer.next is not None:
if pointer.val == pointer.next.val:
pointer.next = pointer.next.next
else:
pointer = pointer.next
return head
Delete Node in a Linked List
这一题tricky 的地方是你不能拿到前面的节点,所以就换点要删掉的节点的值,连向下一个.
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
if node is None or node.next is None:
return
node.val = node.next.val
node.next = node.next.next
另外有一种很重要的特性是环形,头结点和尾节点相连.这两题都是 CC150的经典题.
class Solution:
# @param head, a ListNode
# @return a boolean
def hasCycle(self, head):
fast, slow = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: return True
return False
Linked List Cycle II
这一题主要想明白这个公式是怎么来的,
class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
fast, slow = head, head
while fast and fast.next: # prevent infinite loop
slow = slow.next
fast = fast.next.next
if fast is slow: break
# X is length before cycle, Y is length of cycle
# for slow: total distance is X + nY
# meet at K point
# X + K = (m - 2n)Y
if not fast or not fast.next: return None # no cycle
slow = head
# move X steps
while slow is not fast:
slow = slow.next
fast = fast.next
return fast
