removeKFromList.java

/*
Note: Try to solve this task in O(n) time using O(1) additional space, where n is the number of elements in the list, since this is what you'll be asked to do during an interview.

Given a singly linked list of integers l and an integer k, remove all elements from list l that have a value equal to k.

Example

For l = [3, 1, 2, 3, 4, 5] and k = 3, the output should be
removeKFromList(l, k) = [1, 2, 4, 5];
For l = [1, 2, 3, 4, 5, 6, 7] and k = 10, the output should be
removeKFromList(l, k) = [1, 2, 3, 4, 5, 6, 7].

*/

// Definition for singly-linked list:
// class ListNode<T> {
//   ListNode(T x) {
//     value = x;
//   }
//   T value;
//   ListNode<T> next;
// }
//
ListNode<Integer> removeKFromList(ListNode<Integer> l, int k) {
    ListNode<Integer> tmp = new ListNode<Integer>(0);
    ListNode<Integer> prev = null;
    //tmp = null;
    ListNode<Integer> head = tmp;
    while(l != null){
        if(l.value != k){
            tmp.next = l;
            tmp = tmp.next;
            tmp.value = l.value;
            prev = l;
        }
        if(l.next != null){
            if(l.next.next == null && l.next.value == k){
                tmp.next = null;
            }
        }
        l = l.next;
    }
    return head.next;
}