@TOC

题目描述

题目1（83. 删除排序链表中的重复元素）

题目2（82. 删除排序链表中的重复元素 II）

解题思路

题目1（83. 删除排序链表中的重复元素）

使用指针pre遍历链表，比较当前 pre.val与 pre.next.val是否相同，如果相同则删除pre.next节点（pre.next = pre.next.next）。

题目2（82. 删除排序链表中的重复元素 II）

• 使用三个指针（left,mid,right）遍历链表，如果mid.val与left.val和right.val都不相等，则将mid节点插入到新链表的链尾。
• 对于第一个节点，只需要比较它与第二个节点的元素是否相同，如果不同，则将第一个节点插入到新链表的链尾。
• 同理，对于最后一个节点，只需要比较它与倒数第二个节点的元素是否相同，如果不同，则将最后一个节点插入到新链表的链尾。

代码实现

题目1（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) {
        //链表为空或只有一个节点时，直接返回head
        if (head == null || head.next == null) {
            return head;
        }

        ListNode pre = head;
        while (pre.next != null) {
            if (pre.val == pre.next.val) {
                pre.next = pre.next.next;    //删除pre.next指针
            } else {
                pre = pre.next;
            }
        }

        return head;
    }
}

题目2（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) {
            //链表为空或只有一个节点时，直接返回head
        if(head == null || head.next == null) return head;
        //链表只有两个节点时，只需比较前两个节点
        if(head.next.next == null){
            if(head.val == head.next.val) return null;
            else return head;
        }
        ListNode res = new ListNode(0);
        ListNode temp = res;
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //针对第一个和第二个节点的比较
        if(head.val != head.next.val){
            temp.next = head;
            temp = head;
        }
        while(right != null){
            if(mid.val != left.val && mid.val != right.val){
                temp.next = mid;
                temp = mid;
            }
            left = left.next;
            mid = mid.next;
            right = right.next;
        }
        //遍历结束时，mid和left就分别指向最后一个和倒数第二个节点
        //针对最后一个和倒数第二个节点的比较
        if(mid.val != left.val){
            temp.next = mid;
            temp = mid;
        }
        temp.next = null;

        return res.next;
    }
}