Remove Duplicates from Sorted List

这个题其实很简单,就是按顺序遍历一遍找重复的元素,用两个pointer,一个是current,一个是next。
如果current和next不相同,那么current和next都各进一步,
如果发现current和next相同,那么current直接指向next.next,之后next进一步。
注意检查next是否是null,如果是的话,next.next就会找不到指针,注意结束。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        if (current == null)
            return head;
        else
        {
            ListNode next = current.next;
            while(next != null) // notice that if found duplicate, only move next, current stay the same
            {
                if (current.val == next.val)
                {
                    current.next = next.next;
                    next = next.next;
                }
                else
                {
                    current = next;
                    next = next.next;
                }
            }
        }
        return head;
    }
}

Another submission

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode p = head;
        while(p.next != null) {
            if (p.next.val == p.val) //remove
                p.next = p.next.next;
            else {
                p = p.next;
            }
        }
        return head;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s