Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

赋值法

复杂度

时间 O(1) 空间 O(1)

思路

乍一看没法获取上一个链表节点，似乎无法将当前结点去除。实际上只要将下一个节点的值覆盖当前节点，然后删除下一个节点就好了。注意这样不适用于尾节点。

代码

public class Solution {    public void deleteNode(ListNode node) {        node.val = node.next.val;        node.next = node.next.next;    }}

Remove Linked List Elements

伪造表头

复杂度

时间 O(N) 空间 O(1)

思路

删除链表所有的特定元素的难点在于如何处理链表头，如果给加一个dummy表头，然后再从dummy表头开始遍历，最后返回dummy表头的next，就没有这么问题了。

代码

public class Solution {    public ListNode removeElements(ListNode head, int val) {        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode curr = dummy;        while(curr.next!=null){if(curr.next.val == val){    curr.next = curr.next.next;} else {    curr = curr.next;}        }        return dummy.next;    }}