CODEWITHSUNDEEP
javalinked-list
Dc Redwing
Dc Redwing

Reputation: 1791

Linked List: definition of .next and temp linkedlist node

I am solving the problem in the interview question about LinkedList.

question is...

Write code to remove duplicates from an unsorted linked list FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

I was reading the solution and I dont understand three parts in the solution.

First, 

public static void deletedup(LinkedListNode n) 
{
     Hashtable table = new Hashtable();
     LinkedListNode prev = null;
     while(n != null)
     {
         if(table.containsKey(n.data))
          prev.next = n.next; //<--
          else
          table.put(n.data, true);
          prev = n;//<--
      }
       n =  n.next;
}

First-1 question. In the solution, if table contains the duplicated keyword. they have move to next node. I was thinking the we just need to to n = n.next. However, solution was doing prev.next= n.next;. However, we don't really sure prev in the code. Why do we have to use prev ? Moreover, after putting unique keyword in the table solution assign n to prev (prev = n;). Why do we have to do it ?

Second, 

public static void deletedup(LinkedListNode head)
{ 
LinkedListNode pre = head;
LinkedListNode cur = pre.next;
while(cur != null){ 
  LinkedListNode runner =head;
while(runner != current)
{
  if(runner.data == cur.data)
  { 
      LinkedListNode tmp = current.next;
      pre.next = tmp;//<---
      current = tmp;//<--
      break;
  }
  [...]
}

[...]
}
}

Second question , from the second solution , it program find the duplicated keywords, we have to remove it. Therefore, they declare tmp node to remove to remove duplicated keyowrds. However, I don't really understand the reason to do " pre.next = tmp and cur = tmp". I am guessing thet "cur = tmp" will update the current to next node. However, I am not really sure about the reasons..

Third, for the Big o part . I am assuming that first solution will be O(n) and second solution will be O(n^2). Is it right ?

thanks

Upvotes: 1

Views: 2787

Answers (2)

alienprogrammer
alienprogrammer

Reputation: 28

First Question: n is a reference to a node. It is a local reference that is only valid in this function.

Say we are accessing the linked list in the future. The way a node is discovered is by the reference 'r' located in the previous node. We need to change that reference. If we change n, it will not make any difference to 'r'.

If you're from the C/C++ world, think of n as being like a unique pointer to a node. Will changing the value of this pointer change the value of 'r'? I think not.

Second Question: I think your doubt here might be related to assignments. WHen we say 'current.next', we are referring to the 'next' variable in object 'current'. We are not saying, 'advance current to the next node'. That is why 'current.next' will not really change any variables. When we say 'current = current.next', we are saying, okay, i want to change the node that 'current' is pointing to, and i want to change it to 'current.next', the next node.

Also, I believe you are right about the complexity.

Upvotes: 1

amit
amit

Reputation: 178491

first question:

n = n.next has no no affect on the list itself - it will only advance the value of the variable n to its following element, without touching the actual elements in the list.

Doing prev.next= n.next is updating the field next in the object which prev references to - and putting the value of n.next [which is a reference to an object] there.

second question:

Same issue, curr = temp will have no affect on the list, it will only modify the value of the variable.

Upvotes: 1

Related Questions