影响网站排名原因,一个网站如何做推广方案设计,wordpress 软件公司,办公室装修费用题目
给定一个已排序的链表的头 head #xff0c; 删除原始链表中所有重复数字的节点#xff0c;只留下不同的数字 。返回已排序的链表 。
示例 1#xff1a; 输入#xff1a;head [1,2,3,3,4,4,5] 输出#xff1a;[1,2,5]
示例 2#xff1a; 输入#xff1a;head …题目
给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回已排序的链表 。
示例 1 输入head [1,2,3,3,4,4,5] 输出[1,2,5]
示例 2 输入head [1,1,1,2,3] 输出[2,3]
提示 链表中节点数目在范围 [0, 300] 内 -100 Node.val 100 题目数据保证链表已经按升序排列 思路
上一题重复节点只保留一个向后多看一个节点。
本题重复节点一个都不留向后多看多个节点。
当前情况不能用prev和cur来判断重复节点此时prev引用一定指向不重复的节点需要再引入一个next引用。向后多走几步
当链表中只有一个节点next null不可能出现重复元素。当cur.val ! next.val时说明cur不是重复节点三个引用都向后移动一个单位。当cur.val next.val时让next继续向后走直到next指向与cur.val不相等的节点。此时prev到next之间全是需要删除的元素prev.next next; 当且仅当cur.val ! next.val才能移动prev指针此时cur指向nextnext指向cur.next。
上面3种情况分别对应下面3副图 代码
/*** 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) {ListNode dummyHead new ListNode(101);dummyHead.next head;ListNode prev dummyHead;ListNode cur prev.next;while(cur ! null) {ListNode next cur.next;if(next null) {//此时链表中只有一个元素不可能出现重复元素return dummyHead.next;} else if(cur.val ! next.val) {//此时cur不是重复节点三个指针都向后移动一个单位prev prev.next;cur cur.next;} else {//此时cur.val next.val让next指针一直向后移动直到与cur.val不相等的节点位置为止while(next ! null cur.val next.val) {next next.next;}//此时next指向了第一个不重复的元素prev到next之间所有元素全部删除prev.next next;cur next;}}return dummyHead.next;}
}
