Как поменять местами узлы в односвязном списке

Поменять местами два элемента односвязного списка

В односвязном списке нужно найти элемент, удалить его и поменять местами два следующих. С первой частью задания справился, но не могу поменять местами два следующих элемента. Подскажите, пожалуйста, как это можно сделать? Структура:

struct SingleList < int Data; SingleList *Next; >; 

Отслеживать
user252108
задан 28 мая 2017 в 11:48
user252108 user252108
13 1 1 серебряный знак 4 4 бронзовых знака

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Пусть два следующих не NULL.

// ptr -> a -> b -> c SingleList *a = ptr->Next; SingleList *b = a->Next; ptr->Next = b; // a -> b -> c // ^ // ptr | a->Next = b->Next; // a -> c // ^ // ptr -> b | b->Next = a; // ptr -> b -> a -> c 

Добавьте необходимую логику в случае если имеется NULL значение и проверку на NULL перед обращением к Next.

Двусвязный список — Основы алгоритмов и структур данных

Вы уже знакомы с односвязным списком. Эта структура данных позволяет быстро вставлять и удалять элементы. Звучит удобно, но такой подход работает не во всех случаях. В этом уроке вы познакомитесь с двусвязным списком, который лучше подходит для некоторых типичных задач в программировании.

Есть несколько задач, для которых односвязный список подходит не очень хорошо. В частности, он несимметричен — если вставка и удаление в начале списка выполняются за константное время

, то в конце — за линейное

. Если в списке будет тысяча элементов, вставка в начало может оказаться в тысячу раз быстрее, чем вставка в конец.

Другая задача, которую трудно решить с помощью односвязного списка — вставка перед заданным узлом. Предположим, у нас есть текст на русском языке, где каждый элемент — либо отдельное слово, либо знак препинания. В тексте могут быть ошибки: например, могут отсутствовать запятые и точки. Мы предполагаем, что если слово начинается с большой буквы, перед ним должна быть точка. Если в тексте есть союзы «но» и «а», перед ними должна стоять запятая.

Расссмотрим такой пример:

«Его» «пример» «другим» «наука» «но» «,» «боже» «мой» «,» «какая» «скука» «с» «больным» «сидеть» «и» «день» «и» «ночь» «,» «не» «отходя» «ни» «шагу» «прочь» «Какое» «низкое» «коварство» «полуживого» «забавлять» «ему» «подушки» «поправлять» «,» «печально» «подносить» «лекарство»

В этом тексте не хватает запятой перед словом «но» и точки перед словом «Какое». Попробуем решить эту задачу с помощью односвязного списка. Нам нужно:

• Поместить слова в односвязный список
• Найти слово «но»
• Попробовать вставить перед ним запятую

Здесь мы сталкиваемся с тем, что в узле нет ссылки на предыдущий элемент, только на следующий:

Односвязный список устроен так, что для вставки запятой между словами «наука» и «но» нужно модифицировать именно узел со словом «наука». Эти детали делают наш возможный алгоритм сложным и медленным.

Для подобных задач лучше использовать списки, в котором хранятся обе ссылки.

Двусвязный список

В каждом узле двусвязного списка хранится две ссылки — на следующий и на предыдущий узел. Кроме того, в нем хранятся ссылки и на голову списка (первый элемент), и на его хвост (последний элемент):

Как и в случае с односвязным списком, нам приходится особым образом хранить ссылку на следующий узел для последнего узла. Там мы помещаем значение null — пустую ссылку, которая ни на что не указывает. На рисунке последний узел в списке — это D.

У первого узла не может быть предыдущего узла, поэтому и здесь мы записываем null вместо ссылки. На рисунке первый узел в списке — это A.

За счет изменения структуры, мы получаем две новые возможности:

• Вставка и удаление в конце списка становятся настолько же быстрыми, как и в начале. Теперь они выполняются за константное время
• Вставка узла перед заданным узлом становится такой же простой операцией, как и вставка после

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

Вставка узла в начало списка

Посмотрим, как выглядит вставка узла в начало списка:

class DoublyLinkedListNode  constructor(value, previous, next)  this.value = value; this.previous = previous; this.next = next; > > class DoublyLinkedList  head = null; tail = null; insertBegin(value)  if (this.head == null)  const node = new DoublyLinkedListNode(value, null, null); this.head = node; this.tail = node; > else  const node = new DoublyLinkedListNode(value, null, this.head); this.head.previous = node; this.head = node; > > >

class DoublyLinkedListNode: def __init__(self, value, previous, next): self.value = value self.previous = previous self.next = next class DoublyLinkedList: head = None tail = None def insert_begin(self, value): if self.head is None: node = DoublyLinkedListNode( value, None, None ) self.head = node self.tail = node else: node = DoublyLinkedListNode( value, None, self.head ) self.head.previous = node self.head = node

php class DoublyLinkedListNode  public function __construct($value, $previous, $next)  $this->value = $value; $this->previous = $previous; $this->next = $next; > > class DoublyLinkedList  public $head = null; public $tail = null; public function insertBegin($value)  if ($this->head == null)  $node = new DoublyLinkedListNode($value, null, null); $this->head = $node; $this->tail = $node; > else  $node = new DoublyLinkedListNode($value, null, $this->head); $this->head->previous = $node; $this->head = $node; > > >

class DoublyLinkedListNode  Object value; DoublyLinkedListNode previous; DoublyLinkedListNode next; DoublyLinkedListNode(Object value, DoublyLinkedListNode previous, DoublyLinkedListNode next)  this.value = value; this.previous = previous; this.next = next; > > class DoublyLinkedList  DoublyLinkedListNode head = null; DoublyLinkedListNode tail = null; public void insertBegin(Object value)  if (head == null)  var node = new DoublyLinkedListNode(value, null, null); head = node; tail = node; > else  var node = new DoublyLinkedListNode(value, null, head); head.previous = node; head = node; > > >

Разберем этот фрагмент кода подробнее.

Двусвязный список, как и односвязный, требует определения двух классов:

Первый класс — DoublyLinkedListNode . Он описывает узел двусвязного списка и состоит из таких компонентов:

• Значения — value
• Ссылки на предыдущий узел — previous
• Ссылки на следующий узел — next

Второй класс — DoublyLinkedList . Он представляет список целиком, вместе с его операциями-алгоритмами. Там находятся:

• Ссылка на первый узел — head
• Ссылка на последний узел — tail
• Различные методы, например:

• insertBegin(value) — вставка в начало
• insertEnd(value) — вставка в конец
• removeBegin() — удаление из начала

Новый список пуст, поэтому поля head и tail содержат значение null :

После вставки первого узла head и tail содержат его адрес. При этом поля previous и next у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла:

Теперь посмотрим на фрагмент кода:

if (this.head == null)  const node = new DoublyLinkedListNode(value, null, null); this.head = node; this.tail = node; >

if self.head is None: node = DoublyLinkedListNode( value, None, None ) self.head = node self.tail = node

php if ($this->head == null)  $node = new DoublyLinkedListNode($value, null, null); $this->head = $node; $this->tail = $node; >

if (head == null)  var node = new DoublyLinkedListNode(value, null, null); head = node; tail = node; >

Условие this.head == null выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям this.head и this.tail .

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

Это довольно сложная логика, которая требует аккуратной реализации и проверки граничных условий. Поэтому код методов двусвязного списка сложнее, чем код методов односвязного. Посмотрите на этот пример:

const node = new DoublyLinkedListNode(value, null, this.head);

node = DoublyLinkedListNode(value, None, self.head)

php $node = new DoublyLinkedListNode($value, null, $this->head);

var node = new DoublyLinkedListNode(value, null, head);

Создавая узел, мы сразу записываем в поле next текущее значение this.head — текущую голову. Поле previous текущей головы должно ссылать на новый узел, за это отвечает такая строка:

this.head.previous = node;

self.head.previous = node

php $this->head->previous = $node;

head.previous = node;

Наконец, новый узел становится новой головой списка:

this.head = node;

self.head = node

php $this->head= $node;

head = node;

Вставка узла в конец списка

Перейдем к вставке узла в конец списка:

insertEnd(value)  if (this.tail == null)  const node = new DoublyLinkedListNode(value, null, null); this.tail = node; this.head = node; > else  const node = new DoublyLinkedListNode(value, this.tail, null); this.tail.next= node; this.tail = node; > >

def insert_end(self, value): if self.tail is None: node = DoublyLinkedListNode(value, None, None) self.tail = node self.head = node else: node = DoublyLinkedListNode(value, self.tail, None) self.tail.next = node self.tail = node

php public function insertEnd($value)  if ($this->tail == null)  $node = new DoublyLinkedListNode($value, null, null); $this->tail = $node; $this->head = $node; > else  $node = new DoublyLinkedListNode($value, $this->tail, null); $this->tail->next= $node; $this->tail = $node; > >

class DoublyLinkedList  // . public void insertEnd(Object value)  if (tail == null)  var node = new DoublyLinkedListNode(value, null, null); tail = node; head = node; > else  var node = new DoublyLinkedListNode(value, tail, null); tail.next= node; tail = node; > > >

Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами head и tail , а также previous и next .

Удаление узла

Перейдем к операциям удаления:

removeBegin()  if (this.head == null)  return undefined; > const result = this.head.value; if (this.head == this.tail)  this.head = null; this.tail = null; > else  this.head = this.head.next; this.head.previous = null; > return result; >

def remove_begin(self): if self.head is None: return None result = self.head.value if self.head == self.tail: self.head = None self.tail = None else: self.head = self.head.next self.head.previous = None return result

php public function removeBegin()  if ($this->head == null)  return null; > $result = $this->head->value; if ($this->head == $this->tail)  $this->head = null; $this->tail = null; > else  $this->head = $this->head->next; $this->head->previous = null; > return $result; >

class DoublyLinkedList  // . public Object removeBegin()  if (head == null)  return null; > var result = head.value; if (head == tail)  head = null; tail = null; > else  head = head.next; head.previous = null; > return result; > >

Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает undefined . В остальных случаях мы сохраняем значение в переменную result :

if (this.head == null)  return undefined; > const result = this.head.value;

if self.head is None: return None result = self.head.value

php if ($this->head == null)  return null; > $result = $this->head->value;

if (head == null)  return null; > var result = head.value;

Если this.head == this.tail , значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить head и tail :

if (this.head == this.tail)  this.head = null; this.tail = null; >

if self.head == self.tail: self.head = None self.tail = None

php if ($this->head == $this->tail)  $this->head = null; $this->tail = null; >

if (head == tail)  head = null; tail = null; >

А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в head ссылку на второй узел, а потом обнуляем у нее поле previous :

this.head = this.head.next; this.head.previous = null;

self.head = self.head.next self.head.previous = None

php $this->head = $this->head->next; $this->head->previous = null;

head = head.next; head.previous = null;

Перебор значений в прямом порядке

Раньше для работы с массивами, связными и двусвязными списками, программисты писали разный код. Например, если надо было просуммировать элементы массива и элементы связного списка, приходилось писать две похожие функции. Каждая из них складывала элементы коллекций, но доступ к этим элементам у массива и списка был разным.

Дублирование кода — одна из самых неприятных вещей в программировании. При внесении правок можно забыть поменять код в одной из копий и это приведет к ошибкам, которые трудно обнаружить. Но есть решение этой проблемы: в языках постоянно появляются новые инструменты, которые помогают избавиться от старых ошибок и реже дублировать код.

Чтобы просуммировать элементы из разных структур данных, сейчас достаточно написать всего одну функцию. Это стало возможным благодаря итераторам. Обычно итерацией в программировании называют отдельный шаг цикла. Но у слова есть и другое значение.

Итератор — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка:

const sum = (items) =>  let result = 0; for (item of items)  result = result + item; > return result; >; console.log(sum([1, 2, 3, 4])); // => 10

def sum(items): result = 0 for item in items: result = result + item return result print(sum([1, 2, 3, 4])) # => 10

php function sum($items)  $result = 0; foreach ($items as $item)  $result = $result + $item; > return $result; >; print_r(sum([1, 2, 3, 4])); // => 10

class App  public static int sum(IterableInteger> items)  var result = 0; for (var item: items)  result = result + (int) item; > return result; > > System.out.println(App.sum(List.of(1, 2, 3, 4))); // => 10

Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор.

Однако, здесь есть проблема. Массив и односвязный список имеют естественный порядок перебора — от начала к концу. В двусвязном списке поддерживаются два равноправных порядка:

• От начала к концу
• От конца к началу

Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод fore() может создавать и возвращать прямой итератор:

fore()  let iterator =  current: this.head >; iterator[Symbol.iterator] = function* ()  while (this.current != null)  yield this.current.value; this.current = this.current.next; > >; return iterator; >

def fore(self): current = self.head while current is not None: yield current.value current = current.next

php public functon fore()  $current = $this->head; while($current !== null)  yield $current->value $current = $current->next > >

Использовать итератор можно так:

let list = new DoublyLinkedList(); list.insertBegin(1); list.insertBegin(2); list.insertBegin(3); list.insertBegin(4); console.log(sum(list.fore())); // => 10

lst = DoublyLinkedList() lst.insert_begin(1) lst.insert_begin(2) lst.insert_begin(3) lst.insert_begin(4) print(sum(lst.fore()))

php $list = new DoublyLinkedList(); $list->insertBegin(1); $list->insertBegin(2); $list->insertBegin(3); $list->insertBegin(4); print_r(sum($list->fore())); // => 10

class DoubleLinkedList implements IterableObject>  // . @Override public IteratorObject> iterator()  return new DoubleLinkedListIterator(); > private class DoubleLinkedListIterator implements IteratorObject>  DoubleLinkedListNode current = head; @Override public Object next()  if (!this.hasNext())  throw new NoSuchElementException(); > var lastReturnedNode = current; current = current.next; return lastReturnedNode.value; > @Override public boolean hasNext()  return current != null; > > > var list = new DoubleLinkedList(); list.insertBegin(1); list.insertBegin(2); list.insertBegin(3); list.insertBegin(4); System.out.println(App.sum(list)); // => 10

В JavaScript используется синтаксис function* и yield , который упрощает работу с итераторами. В нашем примере порядок действий такой:

• Начинаем с первого узла, адрес которого хранится в поле head
• Пробегаем по всем узлам списка
• Передаем значения узлов в вызывающую функцию с помощью конструкции yield

Выводы

• Односвязный список подходит не для всех задач — он предоставляет только последовательный доступ к последующим элементам
• Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список.

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Как поменять местами ноды стека/односвязного списка?

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

#include struct Stack < int value; struct Stack *next; >; void print_stack(struct Stack *head) < struct Stack *h = head; if (h == NULL) return; while (h != NULL) < printf("%d at %p\n", h->value, h); h = h->next; > > struct Stack *swap_min_max_nodes(struct Stack *head) < struct Stack *h = head; if (h == NULL) return head; struct Stack *min = h, *max = h; struct Stack *before_min = NULL, *before_max = NULL; while (h != NULL) < if (h->value < min->value) if (h->value > max->value) h = h->next; > if (before_min) before_min->next = max; if (before_max) before_max->next = min; struct Stack *tmp = min->next; min->next = max->next; max->next = tmp; struct Stack *new_head = head; if (new_head == min) new_head = max; if (new_head == max) new_head = min; return new_head; > int main(void) < //struct Stack a = ; //struct Stack b = ; //struct Stack head = ; struct Stack a = ; struct Stack b = ; struct Stack c = ; struct Stack head = ; print_stack(&head); struct Stack *new_head = swap_min_max_nodes(&head); printf("\n"); print_stack(new_head); return 0; >

• Вопрос задан более года назад
• 562 просмотра

Комментировать
Решения вопроса 1
Разработчик на С++, экс-олимпиадник.

Ну да, вам придется рассматривать отдельный случай — когда они идут подряд. Проверяйте, что а вдруг min->next == max . Нарисуйте картинку из четырех точек before_min, min, max, max->next со стрелочками до помены и после. Смотрите у каких трех вершин ссылки поменяются и как. Запишите это в коде.

Еще есть случай max->next == min , но его можно рассмотреть вместе с предыдущим — просто в этом случае поменяйте месами указатели min и max (а также before_min и before_max). Тогда код для прошлого случая сработает. Вам же в момент помены без разницы, какая вершина максимум, а какая минимум. Вам надо только 2 заданные вершины поменять местами.

Ответ написан более года назад
Sheogorath2 @Sheogorath2 Автор вопроса

Спасибо, теперь понятно

struct Stack *tmp; if (max->next == min) < tmp = min; min = max; max = tmp; tmp = before_min; before_min = before_max; before_max = tmp; >if (min->next == max) < if (before_min) before_min->next = max; min->next = max->next; max->next = min; > else < if (before_min) before_min->next = max; if (before_max) before_max->next = min; tmp = min->next; min->next = max->next; max->next = tmp; >

Ответы на вопрос 0
Ваш ответ на вопрос

Войдите, чтобы написать ответ

• Программирование
• +2 ещё

Хештаблицы, можно ли мешать open addressing и chaining?

• 2 подписчика
• 4 часа назад
• 50 просмотров

Напишите код, разбивающий связный список вокруг некоторого значения так, чтобы все меньшие узлы оказались перед узлами, большими или равными этому значению

Если бы мы работали с массивом, то было бы много сложностей, связанных со смещением элементов.

Со связным списком задача намного проще. Вместо того чтобы смещать и менять местами элементы, мы можем создать два разных связных списка: один для элементов, меньших х, а второй — для элементов, которые больше или равны х.

Мы проходим по списку, расставляя элементы по спискам before и after. Как только конец исходного связного списка будет достигнут, можно выполнить слияние получившихся списков.

Приведенный код реализует данный подход:

/* Передаем начало списка, который нужно разделить, и значение х, вокруг которого * список будет разделен */ public LinkedListNode partition(LinkedListNode node, int x) < LinkedListNode beforeStart = null; LinkedListNode beforeEnd = null; LinkedListNode afterStart = null; LinkedListNode afterEnd = null; /* Разбиваем список */ while (node != null) < LinkedListNode next = node.next; node.next = null; if (node.data < x) < /* Вставляем узел в конец списка before*/ if (beforeStart == null) < beforeStart = node; beforeEnd = beforeStart; >else < beforeEnd.next = node; beforeEnd = node; >> else < /* Вставляем узел в конец списка after */ if (afterStart == null) < afterStart = node; afterEnd = afterStart; >else < afterEnd.next = node; afterEnd = node; >> node = next; > if (beforeStart == null) < return afterStart; >/* Слияние списков before и after */ beforeEnd.next = afterStart; return return beforeStart; > 

Если вы не хотите использовать четыре переменные, чтобы отслеживать всего два связных списка, можно избавиться от части из них за счет небольшой потери эффективности. Но «ущерб» будет не очень велик, оценка алгоритма по времени останется такой же, зато код станет более коротким и красивым.

Альтернативное решение: вместо вставки узлов в конец списков before и after можно вставлять элементы в начало списка.

public LinkedListNode partition(LinkedListNode node, int x) < LinkedListNode beforeStart = null; LinkedListNode afterStart = null; / Разбиваем список */ while (node != null) < LinkedListNode next = node.next; if (node.data < x) < /* Вставляем узел в начало списка before */ node.next = beforeStart; beforeStart = node; >else < /* Вставляем узел в начало списка after */ node.next = afterStart; afterStart = node; >node = next; > /* Выполняем слияние списков */ if (beforeStart == null) < return afterStart; >/* Находим конец списка before и соединяем списки*/ LinkedListNode head = beforeStart; while (beforeStart.next != null) < beforeStart = beforeStart.next; >beforeStart.next = afterStart; return head; return head; > 

Обратите внимание на нулевые значения. В строке 7 добавлена дополнительная проверка. Необходимо сохранить следующий узел во временной переменной так, чтобы запомнить, какой узел будет следующим.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»