这里我把删除有关的放在一起讲.

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的经典题.

Linked List Cycle

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