singly-linked list data structure in Java

Question

I am confused about the last "return" statement in the Java implementation of linked list below.

here is the code:

//remove the node with duplicate data and return the linked list
static Node removeDuplicates(Node head) {

 if(head == null)
    return head;

  Node temp = head;
  while(null != temp.next) {
      if(temp.data == temp.next.data)
          temp.next = temp.next.next;
      else
          temp = temp.next;
  }
  return head;
}

The last "return" statement is "return head", but shouldn't it be "return temp"?? My explanation would be that temp node is created to copy the head node, and traverse the entire linked list. At the end of this operation, it is the temp that is modified if there is any duplicate data, so the last statement should be "return temp".

The code above that I am confused about is actually correct, can anyone explain it to me?

Thank you!

Adi Levin Adi Levin · Accepted Answer · 2016-01-24T21:21:30

A handle to a linked list is always the head of the list. The code doesn't reverse the list. It only removes duplicates. More precisely, if temp.data is identical to temp.next.data, then temp.next is being removed. The head of the list is never changed in this process, therefore it is correct to return the original head, since it is also the head of the modified list.

For instance, suppose the original list was head --> a --> b --> c, where head,a,b,c all denote nodes in the list, and suppose the the value of a is identical to the values of b. To remove duplicates, we effectively change the "next" pointer in a to point to c instead of b. This yields the modified list head --> a --> c. The head node of this list is identical to the head node of the original list, and this is why we return head.

singly-linked list data structure in Java

1 Answers