LeetCode-203移除链表元素-Remove-LinkedList-Elements

2次阅读

共计 2018 个字符，预计需要花费 6 分钟才能阅读完成。

删除链表中等于给定值 val 的所有节点。

Remove all elements from a linked list of integers that have value val.

示例:

 输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

两种方法，一种是迭代法，从第一个节点开始，遇到值相同的节点就将其删除。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。

第二种方法是递归，用递归从后向前遇到相同节点直接指向该节点的下一个节点的地址即可

由于链表删除操作的特殊性，如果要删除某个节点，必须要知道该删除节点的前一个节点地址才可完成删除操作。所以如果是从第一个节点开始判断，就要考虑到第一个节点是否为空节点、第一个节点是否就是该删除的的节点，删除头节点和非头节点的操作不一样，应单独实现删除操作。

如果原链表是这种形式：1->1->1->2 val=1 删除头节点后第二个节点置为头节点，但是第二个节点作为新的头节点依然需要删除，所以对头节点的操作应该是一个迭代过程。

另外一种方法就是新建一个虚拟节点，该虚拟节点下一个节点指向原链表头节点。这就无需考虑头节点是否为空、是否为待删除节点。如原链表为：1->1->1->2 val=1，新建一个虚拟节点 -1 作为头节点：-1->1->1->1->2 val=1，这时只需正常迭代删除即可，唯一要注意是返回节点不能是 head，因为原链表的头节点如果是待删除节点，此时 head 节点已被删除并作为单独隔离出来的节点，并非链表内的一个节点。

Java：

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode newHead=new ListNode(-1);// 新建虚拟节点
        newHead.next=head;// 虚拟节点作为原链表的头节点
        ListNode cur = newHead;// 遍历节点的指针

        while (cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;// 删除操作} else {cur = cur.next;}
        }
        return newHead.next;// 返回的头节点应当是虚拟节点的下一个节点
    }
}

Python3：

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        newHead = ListNode(-1)
        newHead.next = head
        cur = newHead
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return newHead.next

递归方法解该题很简单，基线条件是遇到空节点（最后一个节点），递归时只需将传递参数节点的下一个节点作为新的参数传给递归函数即可：

如原链表为：1->2->6->3->4->5->6, val = 6
递归到空节点时最后一个递归函数返回 null：1->2->6->3->4->5->6->null
回到上一层递归函数内此时 head.next 得到返回节点 null
判断 head 为 6 删除，返回 head.next：1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点依然为 null
判断 head 为 5 不删除，返回 head 为 5：1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点 5
判断 head 为 4 不删除，返回 head 为 4：1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点 4
…………..

直到回到第一个递归函数为止返回头节点结束。

Java：

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) return null;// 基线条件
        head.next = removeElements(head.next, val);
        if (head.val == val) {return head.next;} else {return head;}
    }
}

Python3：

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head: return None
        head.next = self.removeElements(head.next, val)
        if head.val == val:
            return head.next
        else:
            return head