• Post Reply Bookmark Topic Watch Topic
  • New Topic

Swap node in Linked List  RSS feed

 
Carmine Gendry
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey guys, back again with another problem. I'm given the following task:
Complete the following method so that it implements a swap between two adjacent elements by adjusting only the links (and not the data) using a single linked list.


I understand that this is what I need it to do:
Original: [1] > [4] > [8] > [7]
Result: [4] > [1] > [7] > [8]

I'm having difficulties completing this method.

I'm not understanding what the node 'beforep' that we are passing is into the method? By the description of the problem wouldn't 'beforep' be null since it's the value before the two nodes that we are starting at?
This is my thinking so far:
node p.next = node afterp.next;
node afterp.next = node p

I'd appreciate any help in getting this started.
Thanks!

 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carmine Gendry wrote:
I'm not understanding what the node 'beforep' that we are passing is into the method? By the description of the problem wouldn't 'beforep' be null since it's the value before the two nodes that we are starting at?


Well, in my speculation (and it is speculation because I don't know how your linked list is implemented), it will not be possible to swap the first two nodes of the list.

Regardless, you probably won't need to anyway. Why? Well...

Assuming that you implemented the linked list by having a special "head" reference, then that would be an edge case. You will need to handle swapping the first node differently than the rest.... so, that may be a different method (or should be).

Assuming that you implemented the linked list by having a node, as the "head" reference, then it wouldn't be necessary to swap the first node. Since the first node is a special node just to point to the actual "first" node, then it wouldn't have a value in this case.

Assuming a completely different implementation, well, then you will need to show us...

Henry
 
Junilu Lacar
Sheriff
Posts: 11485
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, if the list were implemented using a detached Node to point to the "head" node, wouldn't the only corner cases be the ones where "beforep" is one of the last two nodes in the list? If either one of them is the "beforep" node, there won't be 2 nodes after it to swap.
 
Junilu Lacar
Sheriff
Posts: 11485
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, let's say you have this:

 
Junilu Lacar
Sheriff
Posts: 11485
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP, do you know the general algorithm for swapping two things in Java?  In Java and most other languages, swapping two things A and B is not as simple as:

This is true for whatever kind of thing a and b happen to be.  On line 1, you assign b to a.  On line 2, you intended to assign the old value of a to b.  However, you don't have the old value of a anymore because it has a new value when line 2 is executed, which is the value of b.  So if you try to do this to swap two values, you end up with the variables both being the first value assigned to the other value.  Clear as mud?

So what are you going to do? That is the big question that you need to figure out if you don't already know it.
 
Junilu Lacar
Sheriff
Posts: 11485
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wrote:In Java and most other languages, swapping two things A and B is not as simple as...

Just as a point of interest, the Go language and Python allow you to do this:

This is NOT valid syntax in Java, however, so you'll have to figure out a slightly less direct (i.e., more roundabout) way.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!