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 : 遞歸法
- 標準開頭，如果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;}
}
