82. Remove Duplicates from Sorted List II

题目：

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

链接： http://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

题解：

链表去重II，这里要建立一个fake head，因为假如全部为重复，需要移除所有的元素。还需要一个boolean变量来判断当前状态是否重复。最后判断循环结束时的边界状态。

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if(head == null || head.next == null)

            return head;

        ListNode dummy = new ListNode(-1);

        ListNode node = dummy;

        boolean isDuplicate = false;

        while(head.next != null) {

            if(head.next.val == head.val)

                isDuplicate = true;

            else {

                if(!isDuplicate) {

                    node.next = head;

                    node = node.next;

                } else

                    isDuplicate = false;

            }

            head = head.next;

        }

        if(isDuplicate)

            node.next = null;

        else

            node.next = head;

        return dummy.next;

    }

}

二刷：

我发现自己的思路就是和自己的思路一样...磨蹭了半天，二刷还是写了跟一刷很类似的code....

我们主要就是用一个boolean hasDuplicate来记录之前是否出现过重复，以及一个dummy节点来保证假如链表头有重复我们也可以处理。

先做边界判断
建立fake head dummy，以及 node = dummy
在head != null以及 head.next != null的条件下我们进行遍历
假如head.val == head.next.val，我们判定hasDuplicate = true
否则head.val != head.next.val，这时候我们要进行分析
1. 假如hasDuplicate =false，这时候我们这个head可以加入到结果之中去，我们执行node.next = head, node = node.next
2. 否则我们不管
3. 这时候重置hasDuplicate = false
每次head = head.next
最后判断最后一个元素，hasDuplicate为真时，我们把node.next设置为null,跳过最后一个重复元素，否则node.next = head，返回结果

Java:

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if (head == null || head.next == null) {

            return head;

        }

        ListNode dummy = new ListNode(-1);

        ListNode node = dummy;

        boolean hasDuplicate = false;

        while (head != null && head.next != null) {

            if (head.val == head.next.val) {

                hasDuplicate = true;

            } else {

                if (!hasDuplicate) {

                    node.next = head;

                    node = node.next;

                }

                hasDuplicate = false;

            }

            head = head.next;

        }

        node.next = hasDuplicate ? null : head;

        return dummy.next;

    }

}

三刷:

思路跟上面都差不多

Java:

Time Complexity - O(n)， Space Complexity - O(1)。

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);

        dummy.next = head;

        ListNode node = dummy;

        int count = 1;

        while (head != null && head.next != null) {

            if (head.val != head.next.val) {

                if (count == 1) {

                    node.next = head;

                    node = node.next;

                }

                count = 1;

            } else {

                count++;

            }

            head = head.next;

        }

        node.next = (count == 1) ? head : null;

        return dummy.next;

    }

}

巴特西

82. Remove Duplicates from Sorted List II

最新文章

热门文章