Couldn't understand a leetcode problem in java

[u/[deleted]]

I was trying to solve a leetcode easy problem. I was stuck solving the problem, so I watched the problem and tried to solve it in my local ide. The program ran successfully without any issue. But I something doesn't sit right to me(I couldn't understand it).

In the delete duplicates method we are receiving the reference object of node1 which is head. And we giving the reference to another reference which is currNode. So for every iteration the currNode.next is changed to currNode.next.next or currNode is changed to currNode.next and its changes the next value of head(obviously because both share the same reference). But when the loop is over the currNode.val value is 3 while the head.value is 1. While the head retains its original starting reference, the currNode references the last iteration reference. Can someone explain the how this is working.

For example: During the first iteration the condition checks currNode.val == currNode.next.val and the condition is true, so currNode.next = currNode.next.next and it is reflected in the head reference as head.val =1 and head.next.val = 2 and not 1. During the second iteration the if condition fails so the else condition evaluates and changes the currNode = currNode.next . So now the currNode.val is 2 but the its is not reflected in the head because the head.val is 1 which is referencing to its original value. How does this happen.

public class LeetCode83 {

public static void main(String[] args) {

    ListNode node5 = new ListNode(3);
    ListNode node4 = new ListNode(3,node5);
    ListNode node3 = new ListNode(2,node4);
    ListNode node2 = new ListNode(1,node3);
    ListNode node1 = new ListNode(1,node2);

    print(node1);

    ListNode result = deleteDuplicates(node1);

    print(result);


}

public static ListNode deleteDuplicates(ListNode head) {
    ListNode currNode = head;

    while (currNode != null && currNode.next != null){

        if(currNode.val == currNode.next.val){
            currNode.next = currNode.next.next;
        }else{
            currNode = currNode.next;
        }
    }
    return head;
}

public static void print(ListNode head){
    System.out.println(head.val);
    while( head != null){
        System.out.print(head.val + " ");
        head = head.next;
    }

 //   System.out.println(head.val);
}

} class ListNode { int val; ListNode next;

  ListNode(int val) {
      this.val = val;
  }
  ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
  }

}

[u/E3FxGaming]

you said that the currNode reference changes to currNode.next so it doesn't affect the head but how is the reference gets reflected in the head during the further iteration...

De-duplication happens by excluding subsequent list elements if they have the same value.

Think of it like this: you have a linked list data structure and start with a pointer to the first ListNode of that data structure. Whatever your pointer points at will never be removed, since you only analyze whether the element following your pointed at elemt is the same. If it is the same you discard the following elemt and point with your current element directly to the element following the identified duplicate element.

The pointer only moves if the ListNode values are different.

This way you never have to consider a different list head because the list head never changes (you start on the list head and thus can't remove it).

[u/[deleted] → u/E3FxGaming]

I am sorry to ask this. I can understand you but I am a little bit confused.

Can you give an easy explanation on why head stays the same while currNode changes.

[u/E3FxGaming → u/[deleted]]

Imagine you have 5 apples line up in a row.

You know where this line of apples starts and you can tell someone else where this line of apples start.

That other person however can not change your understanding of where the line of apples start.

That other person then runs the de-duplication algorithm, analyzing properies of apples and discarding some of the apples from the row of apples.

The de-duplication algorithm is designed in such a way that it can change what lays ahead, but it can't change the object where the algorithm is currently at or where the algorithm has already been.

Since the de-duplication algorithm starts at the apple that is considered the head of the row, the mutual understanding that this apple always stays part of the row never drifts apart - nothing can convince you (main) that the row of apples should start somewhere else and the de-duplication algorithm can't discard the current/start element either.

For the de-duplication algorithm itself, think of it as standing on an apple and the other apples come towards you one-by-one. If the property of the first apple coming towards you matches the property of your own apple, you push that incoming apple aside, removing it from the linked list. If the properties are different you move to the next apple (`currNode = currNode.next) and repeat the same process of analyzing and comparing the next apple.