1. 力扣82 : 删除排序链表中的重复元素
题 :
给定一个已排序的链表的头 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 题目数据保证链表已经按升序 排列1. 给定一个已排
思路1 : 递归法
- 标准开头，如果head为空链表或该链表只有一个节点，直接返回.
- 如果head指向的节点的数据域与其下一个节点的数据域相等，则p记录head的下下一个节点.p节点仍然有可能与head节点的数据域相等.while循环.如果p的数据域与head的数据域相等，则将head后移一个节点.如果不相等，则跳出循环.因为p之前的节点按照规则都需要删除.所以需要返回p的节点的递归结果.
- 如果head指向的节点的数据域与下一个节点的数据域不想等，则head连接head的下一个节点的递归结果.并返回head.
解1 :
class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } if (head.val == head.next.val) { ListNode p = head.next.next; while (p != null) { if (p.val == head.val) { p = p.next; } else { break; } } return deleteDuplicates(p); } head.next = deleteDuplicates(head.next); return head; } }
思路2 : 一次遍历(官方题解)
- 头节点有可能被删除，所以设置哨兵节点dummy.cur被初始化指向哨兵节点.问题变为判断cur.next与cur.next.next是否需要删除.第一次循环时，判断第一个节点的数据域是否与第二个节点相等，如果相等，p指向第二个节点的next节点.如果p为null，cur.next指向null.如果不相等，判断p节点的数据域是否与cur.next的数据域相等，如果相等，则指向的该节点也需要删除，即p＝p.next.如果不想等，退出内层循环，cur.next指向p.(如出现1 2 2 2 3这种情况).
- 当最后一次while循环时，此时cur指向链表的倒第三个节点.判断cur.next的数据域是否与cur.next.next的相等.如果相等，p为null.则cur.next＝null.如果不想等，倒第一和二的节点无需删除.cur＝cur.next.while条件不满足.退出循环.
解2 :
class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(10086, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { ListNode p = cur.next.next.next; while (p != null) { if (p.val == cur.next.val) { p = p.next; } else { break; } } cur.next = p; } else { cur = cur.next; } } return dummy.next; } }
