【算法训练-链表 四】【链表删除】：删除链表的倒数第N个节点、删除有序链表中的重复元素、删除有序链表中的重复元素II

输入：
{1,2},2    
返回值：
{2}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 1 入参校验及哨兵节点设置
        if (head == null) {
            return null;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // 2 定义快慢指针，都从表头出发
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        // 3 快指针先行N步，拉开与慢指针N个节点间隔
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        // 4 快慢指针同时前进，当快指针到链表尾部的时候，慢指针就对应倒数第N个节点的前一个节点，因为快慢指针拉开的是N个节点距离
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 1-单指针进行链表遍历
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            // 2-只有当前节点和下一节点都不为null才能进行val比较
            if (cur.val == cur.next.val) {
                // 2-1 比较一致则删除下一个节点
                cur.next = cur.next.next;
            } else {
                // 2-2 比较不一致则继续向前搜索，直到cur到链表尾部
                cur = cur.next;
            }
        }
        return head;
    }
}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 1 入参校验
        if (head == null || head.next == null) {
            return head;
        }
        // 2 设置哨兵节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        // 3 双指针遍历
        while (cur != null && cur.next != null) {
            if (cur.val != cur.next.val) {
                // 1-比较不一致则继续前进
                cur = cur.next;
                pre = pre.next;
            } else {
                // 2-比较一致则cur继续向前直到直到不一致的为止
                while ( cur != null && cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 3-删除中间所有的重复节点，cur继续指向新节点
                pre.next = cur.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}