首页 > 代码库 > LEETCODE--Remove Duplicates from Sorted List II

LEETCODE--Remove Duplicates from Sorted List II

2024-07-07 13:08:10   224人阅读

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

 

题目要求删除重复的节点，一个不留。

判决条件可以简化成当前节点和前一个，后一个都不一样时保留，否则删除。

关键在处理各种纷乱的指针：

1. prev这个指针存最后结果的链表。但是由于是根据之前链表改的，所以它的next最开始没有指定，其实还是是指向head的。若不加以修改，如{1,1}本应返回空，却返回了{1}。

2. 前一个需要一个previous存，后一个不需要新建指针存，直接head.next即可。在判决条件中head.next为空退出，即当前head已经是最后一个节点了。在退出时做好最后一步工作。

3. 最后一步工作即为比较当前节点和前一个节点（后一个节点为空不用比较）。若不同则prev的下一个节点肯定就是他，若相同，则prev下一个节点一定要制空，否则其prev下一个节点就为原链表中prev位置的next。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode tempHead = new ListNode(-1000);
        ListNode prev = tempHead;
        ListNode previous = tempHead;
        //tempHead.next = head;
        int flag = tempHead.val;
        //head = head->next;
        while(head.next!=null){
           if (head.val!=previous.val&&head.val!=head.next.val){
               prev.next = head;
               prev = prev.next;
           }
           previous = head;
           head = head.next;
        }
        if (head.val!=previous.val){
            prev.next = head;
        }
        else{
            prev.next = null;
        }
        return tempHead.next;
        
    }
}

 


联系
我们