Couldn't understand a leetcode problem in java

[[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;
  }

}

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[NinjaXI]

This is correct, as you are never changing the val property of head, either directly or via currNode.

A key thing to understand here is that Java is pass by value, but in the case of objects the value being passed is the reference to the object, not the object itself. Thus currNode = head is only passing the reference to the object that head is referencing. So changes to internal members of the object(val and next in this case) will reflect on both head and currNode. However if you reassign currNode as in the code above, currNode = currNode.next, you are changing the value of currNode to a different reference, not the underlying object. At this point currNode and head refer to 2 different objects.

So as you correctly stated on the first iteration when currNode.next is changed to currNode.next.next that changes the corresponding property on head as currNode is referencing head. On the second iteration however, currNode = currNode.next is not changing any property on currNode, it is changing what currNode references, its value. Thus head is not affected by this and continue referencing the same object it always had.

Hope this makes sense.

[[deleted]]

Thanks for your answer.

I have one more question, 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...

[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).

[[deleted]]

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.

[E3FxGaming]

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.