поменяйте местами последние два узла односвязного списка

Question

Как мне поменять последние два узла связанного списка? Я пытаюсь использовать вспомогательный узел, так как считаю, что необходимо избегать «потери» узла в процессе ...

...
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's 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?

Я думаю, что я делаю это неправильно, какие-нибудь намеки?

Answer 1

Предположим, у вас есть связанный список A -> B -> C, и вы хотите поменять местами B и C:

1. Установить T * = B (хранить B где-нибудь)
2. Установите A.next = C
3. Установите T * .next = C.next (это обобщает это просто из работы в конце списка)
4. Установите C.next = T *

Answer 2

Ну, вы уже получили правильный ответ: -)

temp и node4 ссылаются на один и тот же объект.Итак, вы успешно поменяли их местами.Теперь вы можете позволить temp выпадать из области видимости (то есть оставлять его в покое).

Так что вам не нужно ничего устанавливать temp.

Answer 3

Вы на самом деле должны отслеживать три узла - последние два, которые вы будете переключать, и один перед ними, чтобы вы могли обновить его указатель.

Как вариант, вы можетепросто поменяйте местами значения узлов.

Answer 4

Это похоже на односвязный список. Вам нужно сделать node4 преемником node2 (узел, чей преемник был node3). Вам также нужно сделать node3 преемником node4. Итак:

1. Получите ссылки на node2, node3 и node4
2. Установить node2.succ на node4
3. Установить node4.succ на node3
4. Установить node3.succ на null

Вы могли бы сделать это более просто / эффективно (хотя и менее четко), если вы явно не захватываете ссылки на все 3 узла, но это должно помочь вам начать работу.