题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
解题思路:设置一个新的哑元节点result,作为头节点,将head中不重复地节点依次链接到哑元节点后面,最后返回result.next
- 初始值:
- result = new ListNode();
- prev = result
- current = head
- cnt = 0
- 如果current != null,则循环执行:
- 如果 current.next!=null && current.next.val == current.val:说明节点重复
- 令current = current.next
- cnt++:重复节点的数量加1
- 如果 cnt>1 &&(current.next==null || current.next.val != current.val):
- 此时说明有重复的节点,并且current已经到达最后一个重复的节点,但是后面的节点还有可能会出现重复,继续遍历后面的节点,
- current = current.next。
- cnt=0,重新计数
- continue,遍历下一个节点
- prev.next = current:将当前不重复的节点链接到新链表中。
- prev = current:更新前驱
- curent = current.next
- prev.next = null:因为current后面可能还会有重复的节点,所以prev的后继指向null,断开与current后面节点的链接
- 如果 current.next!=null && current.next.val == current.val:说明节点重复
AC代码:
/*** 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) {if (head == null || head.next == null) {return head;}ListNode result = new ListNode();ListNode prev = result;ListNode current = head;int cnt = 0;while (current != null) {if (current.next != null && current.next.val == current.val) {current = current.next;cnt++;if (cnt > 0 && (current.next == null || current.next.val != current.val)) {current = current.next;cnt = 0;}continue;}prev.next = current;prev = current;current = current.next;prev.next=null;}return result.next;}
}
解法二:在头节点前添加一个哑元节点,初始时将current指向哑元节点,如果后面节点有重复的,就一直令current.next = current.next.next,丢弃中间重复的节点current.next,否则令current = current.next,指向下一个不重复的节点
AC代码:
public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode dummy = new ListNode(0, head);ListNode current = dummy;while (current.next != null && current.next.next != null) {if (current.next.val == current.next.next.val) {int value = current.next.val;while (current.next != null && current.next.val == value) {current.next = current.next.next;}} else {current = current.next;}}return dummy.next;}