Friday, August 28, 2015

Leetcode: Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
Understand the problem:
The solution should handle the under cases:
1. If the val is the head, we need a dummy node.
2. If the val to be removed has multiple in consecutive. e.g.
dummy -> 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> null, and val = 1
So we need to iterate over all the elements to be removed until the next non-removed one.
3. If the val to be removed is at the tail. 

Code (Java):
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        
        ListNode p = dummy;
        
        while (p != null) {
            if (p.next != null && p.next.val == val) {
                ListNode q = p.next;
                while (q != null && q.val == val) {
                    q = q.next;
                }
                p.next = q;
            }
            p = p.next;
        }
        
        return dummy.next;
    }
}

No comments:

Post a Comment