Exchange the last two nodes of a singly linked list

Question

How can I swap the last two linked lists? I am trying to use an auxiliary node, since it seems to me that I need to avoid the "loss" of the node in the process ...

... Node node3 = new Node("Hi", null) ; Node node4 = new Node("Hello", null) ; ... // swap node3 & node4 Node temp = node3.succ ; node3.succ = null ; // this should be the last node now, so i set its pointer to null node2.succ = temp ; // the second node successor becomes what used to be the last node temp = node4 ; // not sure how to use temp here. what should it point to if at anything? 

I think I'm doing it wrong, any clues?

Answer 1

Suppose you have a linked list A -> B -> C , and you want to swap B and C :

• Set T * = B (somewhere around B)
• Set A.next = C
• Set T * .next = C.next (this generalizes this from work only at the end of the list)
• Set C.next = T *

Answer 2

This is like a separate list. You need to make node4 successor of node2 (the node whose successor was node3 ). You also need to make node3 successor to node4 . So:

• Get links to node2 , node3 and node4
• Install node2.succ in node4
• Install node4.succ in node3
• Set node3.succ to null

You can do this more simply / efficiently (albeit less clearly) if you obviously do not capture links to all 3 nodes, but this should help you get started.

Answer 3

Well, you have the correct answer :-)

temp and node4 refer to the same object. Thus, you have successfully replaced them. Now you can let temp fall out of scope (that is, leave it alone).

Therefore, you do not need to set the pace for anything.

Answer 4

You really need to keep track of the three nodes — the last two that you switch and the one in front of them so you can update its pointer.

Alternatively, you can simply replace the node values.