删除链表中的重复元素：不留&留一个&删除一个

不留：

［抄题］：

给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。

［思维问题］：

给出 1->2->3->3->4->4->5->null，返回 1->2->5->null

给出 1->1->1->2->3->null，返回 2->3->null

［一句话思路］：

dummy node，防止出现无头链表，不能返回。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

删除链表中的重复元素：不留&留一个&删除一个

［一刷］：

如图，记得删除之后把新的头尾接起来。表达式还是prev.next = crut;但实际存储空间中的箭头是向后指的。
新定义的节点要声明类型：ListNode crut = head;表示把节点内容＋地址都传过去
while循环中应该是crut.next == val，表示当前节点符合就删除，而不是crut.next
取值是.val.。取谁的值，就要判断谁不null。比如crut.val，就判断crut不是null。

［总结］：

记得删除之后把新的头尾接起来。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构，为什么不用别的数据结构］：

［其他解法］：

［Follow Up］：

［题目变变变］：

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;

        while (head.next != null && head.next.next != null) {
            if (head.next.val == head.next.next.val) {
                int val = head.next.val;
                while (head.next != null && head.next.val == val) {
                    head.next = head.next.next;
                }            
            } else {
                head = head.next;
            }
        }
        
        return dummy.next;
    }
}

View Code

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /* * @param head: head is the head of the linked list * @return: head of linked list */ public ListNode deleteDuplicates(ListNode head) { // write your code here if (head == null) { return null; } ListNode node = head; while(node.next != null) { if (node.val == node.next.val) { node.next = node.next.next; } else { node = node.next; } } return head; } }

public class Solution { /* * @param node: the node in the list should be deletedt * @return: nothing */ public void deleteNode(ListNode node) { // write your code here if (node == null || node.next == null) { return ; } ListNode next = node.next; node.val = next.val; node.next = next.next; } }

删除链表中的重复元素：不留&留一个&删除一个

相关推荐