Как обновить тыл в круговом связанном списке?

Question

Мне нужна помощь в обновлении задней части круглого связанного списка, если я переместу набор узлов после начальной задней.

Предположим, что задний - это задний узел, а задний.следующий возвращается обратно к [1].

[1][2][3][4][5]  
<-------------/

Если я перейду [1][2][3] после узла [5], дающего мне

[4][5][1][2][3], который разбивает круговой связанный список,

Как я могу подойти к обновлению [3] в тылу и в тылу, чтобы указать [1]?

Answer 1

Работая на основе того, что вы начинаете с [1] [2] [3] [4] [5] и хотите получить [4] [5] [1] [2] [3], вы можетеделать это с помощью указателей, а не изменять структуру данных.

Как вы указали, у нас есть циклический список, в котором указатель "tail.next" указывает на первое ведро, а каждое последующее ведение имеет указатель .next, связывающий его с его самым правым соседом, пока мы не вернемся копять заднее ведро.По сути, это набор блоков, связанных друг с другом.

Если мы создадим узел "tail" и узел "header", мы можем использовать их для упорядочения списка.Это маркеры, а не часть круга, они просто указывают на начальную или конечную точку.

Таким образом, чтобы получить [1] [2] [3] [4] [5], мы можем установить хвостовой узел наукажите на [5], затем следуйте за следующим указателем [5], который приведет нас к [1], на который мы установили наш заголовок.Таким образом, header = [1]; tail = [5]

Начиная с заголовка и работая со списком, следуя следующим указателям, каждый раз, когда мы можем получить доступ к нашим элементам в этом порядке [1] [2] [3][4] [5].Ничего удивительного!

Давайте изменим это, хотя мы хотим, чтобы [3] был сзади.Итак, давайте установим наш хвостовой узел так, чтобы он указывал на [3].Затем, следуя следующему указателю [3], мы приходим к [4].Для этого мы назначаем header.So header = [4]; tail = [3]

Теперь работаем через наш список, начиная с того, на что указывает наш заголовок [4] [5] [1] [2] [3].

Похоже, мы выполнили операцию перемещения, но мы не вмешивались в нашу структуру данных или ее связи - только в способ, которым мы работаем с ним.Все, что мы изменили, это наш заголовок и хвост.(Наши указатели).Вот в чем красота кругового списка.

Answer 2

Это домашняя работа?

Как вы делаете "движение"?

Я бы сделал это функцией, что-то вроде list.move(first, last, after), которая в данном случае будет list.move(1, 3, 5).

И у вас будут переменные, отслеживающие переднюю / заднюю и заднюю / заднюю часть списка.Я предполагаю, что они называются list.front и list.rear.

Так что в каждом случае вы хотите сделать:

list[after].next = list[first]

, а затем я вижу два особых случая:

• вставка за тылом
  (list[after] == list.rear)
• перемещение головы
  (list[start] == list.front)

Итак, выможет обрабатывать те, которые используют if операторов.

Answer 3

Я думаю, что это отвечает (при условии, что я правильно понимаю)

Node insertAtRear(Node rear, T value) {
  Node tmp = new Node(value);
  if(rear!=null) {
    tmp.next = rear.next;
    rear.next = tmp
    rear = tmp
  } else {
    // this is probably the first element to be inserted
    rear = tmp;
    rear.next = rear;
  }
}

Answer 4

Поскольку набор ссылок является кругом, вам необходимо разорвать ссылки и восстановить их после перемещения. Важными ссылками здесь являются те, которые будут «неработающими», то есть (если это односвязный список, как я предполагаю), ссылка из [3] -> [4] и ссылка из [5] -> [1].

У вас есть два раздела в вашем списке здесь, [1][2][3], который мы можем назвать A, и [4][5], который мы можем назвать B. Ссылка -->, показанная ниже, является указателем на первый элемент в списке.

--> A -> B -+ 
    ^       |
    |       | 
    +-------+

То, что вы хотите сделать, это сбросить ссылку, чтобы последний элемент в A указывал на первый элемент в B, а последний элемент в B указывал на первый элемент в A. Кроме того, начало списка теперь является первым элементом в B.

--> B -> A -+
    ^       |
    |       | 
    +-------+

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

--> [1][2][3] -> [4][5] -+         --> [4][5] -> [1][2][3] -+
     ^                   |    =>        ^                   |
     +-------------------+              +-------------------+

• Установите начало списка как первый элемент B, который равен [4]
• Установите последний элемент в B, который равен [5], чтобы указывать на первый элемент в A, который равен [1]. Это уже установлено таким образом, но не рассчитывайте на это. :)
• Установите последний элемент в A, который равен [3], чтобы указать на первый элемент в B, который равен [4].

Как видите, единственные узлы, которые нас действительно волнуют, - это первый и последний элементы каждой части списка, то есть начальный и конечный элементы A и B. В этом случае один из этих разделов также связан с первым элементом, поэтому нам пришлось перенести понятие, какой элемент был «первым» элементом. Надеюсь, это поможет.