237. 删除链表中的节点

因为在单链表中，无法直接得到一个节点的前驱，因此本题删除的时候，可以进行“移花接木”：

将node后继节点的值赋给node；
然后删除node的后继节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val; // 将node后继节点的值赋给node
        node.next = node.next.next; // 删除node的后继节点
    }
}

剑指 Offer 18. 删除链表的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;

        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
                break;
            }
            p = p.next;
        }

        return dummy.next;
    }
}

203. 移除链表元素

与[上一题](剑指 Offer 18. 删除链表的节点)稍有不同，本题要求删除全部值等于val的值（即链表中的值有重复）。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;

        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
            } else { // 与上一题相比，这里加了else，以防最后一个节点被删导致空指针
                p = p.next;
            }
        }

        return dummy.next;
    }
}

19. 删除链表的倒数第 N 个结点【快慢指针】

快指针先走n步，然后快慢指针一起移动。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode slow = dummy, fast = head;
        int k = 0;

        while (k < n) { // 快指针先走n步
            fast = fast.next;
            ++k;
        }
        
        // 快慢指针一起后移
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 删除(slow的后继节点为要删除的节点)
        slow.next = slow.next.next;

        return dummy.next;
    }
}

2095. 删除链表的中间节点【快慢指针】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        // 慢指针一次走一步，快指针一次走两步，pre标记slow的前驱
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }

        pre.next = slow.next;

        return head;
    }
}

1171. 从链表中删去总和值为零的连续节点【前缀和 + HashMap】

用map记录前缀和与对应节点，如果遇到与之前相等的前缀和，则说明两个节点之间的和为0，需要删除，记得要把map中对应的前缀和删掉。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        if (head == null) {
            return null;
        }

        Map<Integer, ListNode> map = new HashMap<>();
        ListNode dummy = new ListNode(0, head);
        ListNode p = head, tail = head;
        int sum = 0;
        map.put(0, dummy);

        while (p != null) {
            sum += p.val;
            if (map.containsKey(sum)) {
                ListNode node = map.get(sum);
                ListNode removeNode = node.next;
                node.next = p.next;
                int dSum = sum;
                while (removeNode != p) { // 删除map中对应的前缀和
                    dSum += removeNode.val;
                    map.remove(dSum);
                    removeNode = removeNode.next;
                }
            } else {
                map.put(sum, p);
            }
            p = p.next;
        }

        return dummy.next;
    }
}

2181. 合并零之间的节点【双指针】

用一个指针tail标记连续非零元素的第一个节点，用指针p向后遍历，将非零元素的val加到tail上，当p遇到零元素：

将tail指向p的后继节点，即新的连续非零元素的第一个节点（也有可能是空，即表尾）。
如果tail是表尾（tail == null），结束。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p = head.next.next, tail = head.next;
        while (p != null) {
            if (p.val != 0) {
                tail.val += p.val;
                p = p.next;
            } else {
                tail.next = p.next;
                tail = tail.next;
                if (tail == null) {
                    break;
                }
                p = tail.next;
            }
        }

        return head.next;
    }
}

83. 删除排序链表中的重复元素

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode p = head;
        
        while (p != null && p.next != null) {
            if (p.val == p.next.val) { // 跳过p.next这个重复节点
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        
        return head;
    }
}

82. 删除排序链表中的重复元素 II【双指针】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy, p = head;

        while (p != null) {
            while (p.next != null && p.val == p.next.val) { // 略过重复值
                p = p.next;
            }

            if (pre.next == p) { // 上面的while没执行，说明这段没有重复值
                pre = pre.next;
            } else { // 有重复值，此时p指向最后一个重复的值
                pre.next = p.next; // pre不能后移，因为不确定新出现的值是否重复
            }
            p = p.next;
        }

        return dummy.next;
    }
}

面试题 02.01. 移除重复节点【Set】

用HashSet标记该元素是否出现过

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return null;
        }

        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        ListNode p = head.next, tail = head;

        while (p != null) {
            if (!set.contains(p.val)) {
                tail.next = p;
                tail = tail.next;
                set.add(p.val);
            }
            p = p.next;
        }
        tail.next = null;

        return head;
    }
}