Leetcode: 删除排序链表中的重复元素(Java) |
您所在的位置：网站首页 › 单链表删除相同的元素完整代码 › Leetcode: 删除排序链表中的重复元素(Java) |
Leetcode: 删除排序链表中的重复元素(Java)
|
删除链表中的重复元素
题目描述：
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。 返回同样按升序排列的结果链表。 示例：输入：[1,2,2,3,3] 输出：[1,2,3] 思路：链表是已经排序的链表，所以重复的元素在链表中的位置也是连续的。要删除链表中重复的元素只需要遍历链表即可。 让current指向链表的头节点head，current从链表的头节点开始遍历；如果current的值和current.next的值相等，删除current.next;(让current.next 指向 current.next.next)否则，就让current一直往后走，直到current.next == null代码： class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null){ return head; } //不会删除头节点 ListNode current = head; while(current.next!= null){ if(current.val == current.next.val){ current.next = current.next.next; }else{ current = current.next; } } return head; } } 删除链表中重复的元素II 题目描述：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。 返回同样按升序排列的结果链表 示例：
输入：[1,2,3,3,4,4,5] 输出：[1,2,5] 思路：和上面一样，也是通过遍历的方式来删除重复的节点。 由于要将所有重复的元素都删除，所以链表的头节点可能会被删除，所以使用傀儡节点指向链表的头节点。 让prev指向傀儡节点，current指向链表的头节点；遇到current的值和current.next的值相等时，就让current指向current.next如果不相等，就判断prev和current之间有没有节点，没有prev往后走，否则，prev.next指向current.next (跳过重复的元素)只要current不为null,就让current一直往后走。代码： class Solution { public ListNode deleteDuplicates(ListNode head) { //删除排序链表中的重复元素 if(head == null|| head.next == null){ return head; } //可能会删除head节点，所有用虚拟节点 ListNode newHead = new ListNode(-1); newHead.next = head; ListNode prev = newHead; ListNode current = head; while (current != null){ while (current.next != null && current.val == current.next.val){ current = current.next; } if (prev.next == current){ //prev和current之间没有重复的节点，prev向后移动 prev = prev.next; }else { //跳过了重复的元素 prev.next= current.next; } current = current.next; } return newHead.next; } }
|
【本文地址】
今日新闻 |
推荐新闻 |