python's docs

linked list 01: remove from list


1. 题目

Note: Try to solve this task in O(n) time using O(1) additional space, where n is the number of elements in the list, since this is what you'll be asked to do during an interview.

Given a singly linked list of integers l and an integer k, remove all elements from list l that have a value equal to k.

Example

  • For l = [3, 1, 2, 3, 4, 5] and k = 3, the output should be
    removeKFromList(l, k) = [1, 2, 4, 5];

  • For l = [1, 2, 3, 4, 5, 6, 7] and k =10, the output should be
    removeKFromList(l, k) = [1, 2, 3, 4, 5, 6, 7].

Input/Output

  • [time limit] 4000ms (py)

  • [input] linkedlist.integer l
    A singly linked list of integers.
    Guaranteed constraints: 0 ≤ list size ≤ 105, -1000 ≤ element value ≤ 1000.

  • [input] integer k
    An integer.
    Guaranteed constraints:
    -1000 ≤ k ≤ 1000.

  • [output] linkedlist.integer
    Return l with all the values equal to k removed.


2. 解法

个人解法

# Definition for singly-linked list:
# class ListNode(object):
#     def __init__(self, x):
#         self.value = x
#         self.next = None
#

def removeKFromList(l, k):
    new_l = l
    while new_l:
        if new_l.value == k:
            new_l = new_l.next
        else:
            break
    if new_l:
        curr = new_l.next
        last = new_l
        while curr:
            if curr.value == k:
                last.next = curr.next
                curr = last.next
            else:
                last = curr
                curr = curr.next
    return new_l

逻辑不够简洁,有很多多余的逻辑

精品解法

def removeKFromList(l, k):
    curr_node = l
    while curr_node and curr_node.next:
        if curr_node.next and curr_node.next.value == k:
            curr_node.next = curr_node.next.next
        else:
            curr_node = curr_node.next
    return l.next if l and l.value == k else l

linked list是不可迭代对象,逻辑是两个节点一起看,后面节点如果值为k,则将前面节点的next指向更后面一个。
当使用and连接符组成判断条件时,前面的一旦为false,后面的条件不会被检查,这样就避免了很多错误提示。