0
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You don't handle a single element list where head.next == head. You'll be stuck in an infinite loop if that happens. \$\endgroup\$ – mdfst13 Mar 19 '17 at 20:28
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for this approach but the problem did not have a prev and next pointers. \$\endgroup\$ – TheLearner Mar 20 '17 at 5:12
  • \$\begingroup\$ 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 :/ \$\endgroup\$ – Vogel612 Mar 21 '17 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.