Remove Linked List Elements

linked_listLogged into LeetCode and had the site automatically select a challenge for me. It selected Remove Linked List Elements (https://leetcode.com/problems/remove-linked-list-elements/).

Please visit the LeetCode web site to get the description of the challenge. This challenge has a difficulty level set as easy.

From the console of the Eclipse IDE:

show <<< 1 2 6 3 4 5 6

show <<< 1 2 3 4 5

show <<< 2 3 4 5

show <<< 2 3 4

show <<< 2 4

show <<< 4

show <<< 4

show <<<

show <<<

The first line shows the data for the sample case. The linked list contains two instances of number 6. The second line illustrates the result after the values with 6 are deleted. The rest of the lines illustrate additional test cases.

My solution written in Java follows:

package john.canessa.linked.list;

/*

* definition for singly-linked list.

*/

class ListNode {

// ***** elements ****

int           val;

ListNode      next;

/*

* constructor

*/

public ListNode(int x) {

this.val = x;

}

/*

* insert element into list

*/

public ListNode insert(ListNode head, int x) {

if (head == null) {

return new ListNode(x);

} else {

ListNode tail = new ListNode(x);

for (ListNode p = head; true; p = p.next) {

if (p.next == null) {

p.next = tail;

break;

}

}

}

return head;

}

}

public class Solution {

/*

* show the list

*/

static void show (ListNode head) {

System.out.print(“show <<< “);

for (ListNode p = head; p != null; p = p.next) {

System.out.print(p.val + ” “);

}

System.out.println();

}

/*

* remove all elements from a linked list of integers that have value val.

*/

static ListNode removeElements(ListNode head, int val) {

// **** check if list is empty ****

if (head == null) {

return head;

}

// **** loop deleting element(s) with specified value ****

ListNode p = head;

ListNode q = null;

for ( ; p != null; p = p.next) {

// **** check if this element needs to be removed ****

if (p.val == val) {

// **** check if this is the head ****

if (q == null) {

head = p.next;

continue;

}

// **** this is not the head ****

else {

q.next        = p.next;

p             = q;

}

}

// **** skip this element ****

else {

q = p;

}

}

// **** return head of updated list ****

return head;

}

/*

* test code

*/

public static void main(String[] args) {

// **** populate linked list with test data ****

ListNode head = new ListNode(1);

head = head.insert(head, 2);

head = head.insert(head, 6);

head = head.insert(head, 3);

head = head.insert(head, 4);

head = head.insert(head, 5);

head = head.insert(head, 6);

show(head);

// **** remove all elements with the specified value ****

head = removeElements(head, 6);

show(head);

head = removeElements(head, 1);

show(head);

head = removeElements(head, 5);

show(head);

head = removeElements(head, 3);

show(head);

head = removeElements(head, 2);

show(head);

head = removeElements(head, 9999);

show(head);

head = removeElements(head, 4);

show(head);

head = removeElements(head, 9999);

show(head);

}

}

The challenge just requires the contents of the removeElements() method. The rest of the code is just for testing purposes.

If you have comments or questions regarding this blog entry, please do not hesitate and send me a message via email.

John

John.canessa@gmail.com

Follow me on Twitter @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *