LeetCode Study : 83. Remove Duplicates from Sorted List

問題

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

自分の解答

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode header = new ListNode(0);
    header.next = head;
    ListNode currentNode = head;
    head = head.next;
    while (head != null) {
        if (currentNode.val != head.val) {
            currentNode.next = head;
            currentNode = currentNode.next;
        } else {
            currentNode.next = head.next;
        }
        head = head.next;
    }
    return header.next;
}

コード理解

別解

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

Time : / Space :

完全に前回解いたListNodeの問題の悪い影響を受けた。ダミーのheaderを設定して最後header.next返すとか、headの参照そのまま置いとけばやる必要ないもんな〜。 別解シンプルだ。確かにそうだ。 current.next = current.next.next が個人的にはポイント。こうやって値詰めればいいんだ。 currentとhead２つ持つ必要なかったんだよな。う〜ん、なぜシンプルに考えられなかったのか。

指している要素のindexは変化しないけど、その先の要素の数が減っていくパターンが頭の中でしっくり来てなかったのかな。全要素を舐める場合、indexを+1していくパターンしか普段使って来なかったけど、要素を1つ詰めるということでもindex進めずとも舐められるんだよな。

LinkedList扱うときはこの感覚大事にしたい。

今後のための考え方

• LinkedListを総舐めする場合、indexを進めずとも、値を手前に詰めることでも高速に舐められる