Deleting the head node of a circular linked list

Question

Today I tackled this coding challenge:

Given a circular linked list, implement a method to delete its head node. Return the list's new head node.

I would appreciate any feedback.

public ListNode deleteAtHead(ListNode head) {
 if(head == null){
 return head;
 } 
 ListNode temp = head;
 while(temp.next != head){
 temp = temp.next;
 }
 temp.next = head.next;
 head.next = null;
 head = temp.next;
 return head;
}

• mdfst13: You don't handle a single element list where head.next == head. You'll be stuck in an infinite loop if that happens.

Answer 1

Since you are dealing with a circularly linked list (meaning the tail's next points to head and the head's prev points to the tail) and assuming each node has a prev and next, you might consider this easier approach which does not require traversal of the entire list.

public ListNode deleteAtHead(ListNode head) {
 if (head == null) {
 return head;
 }
 ListNode newHead = head.next;
 newHead.prev = head.prev;
 head.prev.next = newHead;
 head.next = null;
 head.prev = null;
 return newHead;
}

This should also work for a list with only 1 node (e.g. a head) assuming it is initialized with prev and next referencing itself.

• TheLearner: Thank you for this approach but the problem did not have a prev and next pointers.
• Vogel612: this doesn't actually correctly solve the given assignment. for head.next == head the correct return value is null, which doesn't happen with your code :/