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

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

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

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

1. меньше двух узлов: вернуть список как есть
2. ровно два узла: поменять узлы местами
3. больше двух: сделать, чтобы последний узел указывал бы на второй узел, а предпоследний — на первый.

где next_to_last() ищет предпоследний узел:

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

Как поменять местами позиции двух узлов в односвязном списке, изменяя только указатели?

Я пытаюсь поменять местами два узла односвязного списка с заданными нулями индексами. В моем коде я обрабатываю много случаев, но этот подход действителен только когда j-i<=2 . Если между i и j есть разница в 3 или более, я не смогу ее обработать.
Пожалуйста, помогите мне исправить мой подход.

3 ответа

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

• Найдите в списке указатели, которые указывают на узлы, которые вы хотите поменять местами. Одним из этих указателей может быть указатель head , но по крайней мере один из них будет указателем next в списке. Помните, что это указатели, которые указывают на узлы, которые вы меняете.
• Поменяйте местами эти указатели
• Поменяйте местами указатели next этих узлов, чтобы восстановить оставшийся порядок в списке.
• Вот и все.

Для этого проще всего использовать указатели на указатели . Это позволяет избежать необходимости полностью обходить указатели prev , что делает алгоритм ужасно более сложным, чем он должен быть.

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

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

Это не сделало бы справедливости без действующего примера. Далее будет построен упорядоченный список из десяти элементов, пронумерованных 1..10. Затем он использует описанную выше процедуру подстановки с нулевым индексом, чтобы поменять местами различные элементы, в частности, что-то, что меняет головной узел, хвостовой узел и некоторые внутренние узлы, а затем отменяет все это, изменяя свопы, чтобы прийти к списку, который мы начали с.

Большинство крайних случаев, которые вы пытаетесь избежать, просто исчезают, если вы помните, что пытаетесь сделать: меняйте указатели, а не узлы. Хитрость заключается в том, чтобы найти указатели (не их значения; фактические указатели), которые указывают на узлы, которые вы хотите поменять, и поменять значения этих указателей.

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

Давай я тебе помогу : —

• Задача 1 — Нахождение i-го индексного узла и j-го индексного узла путем обхода связанного списка (нет необходимости находить расстояние между ними)
• Задача 2 — Замена обоих узлов

Требования — Чтобы поменять узел, получить доступ к его предыдущему узлу (что кажется вам известным, так как вы пробовали это в своем коде)

Некоторые угловые случаи —

• Если я == j или i> j (управляется вашим кодом)
• Если у i-го узла нет предыдущего узла (т. Е. Он возглавляет связанный список)

Теперь попробуйте проанализировать ваш код.

Для справки смотрите код ниже

Надеюсь, это поможет.

Продолжайте спрашивать, продолжайте расти 🙂

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

Односвязный линейный список

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры

Основные действия, производимые над элементами ОЛС:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Удаление корня списка
• Вывод элементов списка
• Взаимообмен двух узлов списка

Инициализация ОЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.

Добавление узла в ОЛС

Функция добавления узла в список принимает два аргумента:

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

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛС включает в себя следующие этапы:

• создание добавляемого узла и заполнение его поля данных;
• переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
• установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Таким образом, функция добавления узла в ОЛС имеет вид:

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЛС

В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЛС включает в себя следующие этапы:

• установка указателя предыдущего узла на узел, следующий за удаляемым;
• освобождение памяти удаляемого узла.

Удаление корня списка

Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

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

• заменяемые узлы являются соседями;
• заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.

При замене соседних узлов переустановка указателей выглядит следующим образом:

При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:

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

Функция взаимообмена узлов списка выглядит следующим образом:

Комментариев к записи: 77

using namespace std;
struct NODE <
char value;
struct NODE* next;
>;

struct DbCircleList <
size_t size;
struct NODE* head;
>;

void addNode(DbCircleList* list, char elem)
<
NODE* newElem = new NODE;
newElem->value = elem;
if (list->size == 0)
<
list->head = newElem;
list->head->next = list->head;
>
else
<
struct NODE* temp;
temp = list->head;
list->head = newElem;
newElem->next = temp;
>
++list->size;
>

void printList(DbCircleList* list)
<
NODE* tmp = list->head;
cout << "List values: " << endl;
for ( int i = 0; i < list->size; ++i)
<
cout << "Value: " << tmp->value << endl;
tmp = tmp->next;
>
>

int main()
<
DbCircleList* list = new DbCircleList;
list->size = 0;
list->head = NULL ;
DbCircleList* list1 = new DbCircleList;
list1->size = 0;
list1->head = NULL ;
DbCircleList* list2 = new DbCircleList;
list2->size = 0;
list2->head = NULL ;

delete list;
delete list1;
delete list2;
return 0;
>

#define _CRT_SECURE_NO_WARNINGS
#include <Windows.h>
#include <stdio.h>
#include <math.h>
#include <malloc.h>

struct book
<
char name[30];
char author[30];
int num_page;
int year;
char style[30];
struct book* next;
>;
struct book* poperedbook, * element, * pershiy, * novii, * ostan;

void Stvorutu( void )
<
element = ( struct book*)malloc( sizeof ( struct book));
pershiy = element;

do
<
poperedbook = element;

printf( "Введіть назву книги, автора, кількість сторінок, рік випуску та стиль \n" );
scanf( "%s %s %d %d %s" , element->name, element->author, &element->num_page, \
& element->year, element->style);

element->next = ( struct book*)malloc( sizeof ( struct book));
element = element->next;
> while (poperedbook->num_page != 0);

ostan = poperedbook;
poperedbook->next = NULL ;
>

void hood( void )
<
element = pershiy;

do
<
//if (element->style == "худ")
// <
printf( "Назва книги: %s , Автор: %s , Кількість Сторінок: %d , Рік випуску: %d , Стиль: %s \n" , \
element->name, element->author, &element->num_page, &element->year, element->style);
poperedbook = element;
element = element->next;
//>
> while (element != NULL );
>

int main()
<
SetConsoleCP(1251);
SetConsoleOutputCP(1251);

struct list <
int ptr;
list *next;
>;

void input_list(list *&first, int n) <
first = new list;
cinn >> first->ptr;
list *q = first;
for ( int i = 0; i < n — 1; i++) <
q->next = new list;
q = q->next;
cin >> q->ptr;
>
q->next = 0;
>
void print_list(list *q) <
while (q) <
cout << q->ptr << " " ;
q = q->next;
>
cout << endl;
>

void razbienie_list(list *&first) <
list *q = first;
list *chet = new list;
list *nechet = new list;
list *q1 = chet;
list *q2 = nechet;
list *w1 = q1;
list *w2 = q2;
while (p) <
if (q->ptr % 2) <
q2->ptr = p->ptr;
q2->next = new list;
w2 = q2;
q2 = q2->next;
>
else <
q1->ptr = p->ptr;
q1->next = new list;
q1 = q1;
q1 = q1->next;
>;
q = q->next;
>
w1->next = 0;
w2->next = 0;
>

int main() <
list *first = 0;
int n = 5;
input_list(first, n);
print_list(first);
razbienie_list(first);
print_list(first);
return 0;
>

#include <iostream>
#include <string>
using namespace std;
const int maxSize = 100;
//Описываем структуру Wood со следующими полями:
//index — номер дерева в базе;
//name — название дерева;
//type — его тип;
//MaximumHeight — максимальная высота;
//lifespan — продолжительность жизни;
struct Wood
<
char name[maxSize];
char type[maxSize];
double MaximumHeight;
double lifespan;
Wood* Next;
>;
Wood* Head;
//Функция для ввода информации об очередном дереве.
void WoodInput( char name[maxSize], char type[maxSize], double & MaximumHeight, double & lifespan)
<
cout << "Name = " ;
cin.get();
cin.get(name, sizeof (name));
cout << "Type = " ;
cin.get();
cin.get(type, sizeof (type));
cout << "MaximumHeight = " ;
cin >> MaximumHeight;
cout << "lifespan = " ;
cin >> lifespan;
cout << endl;
>

//Функция для вывода массива деревьев.
void PrintWood(Wood* Head)
<
Wood* j = Head; // j указывает на начало
while (j != NULL ); // Пока не конец списка
<
cout << "Wood: " << j->name << ";" << j->type << ";" << j->MaximumHeight << ";" << j->lifespan << ";" ;
j = j->Next; // переход к следующему элементу
>
cout << endl;

//Функция для поиска в базе деревьев с определенной продолжительностью жизни.
//Выводит найденные деревья и возвращает их количество.
//Входные параметры:
//ar — массив деревьев;
//n — число деревьев в массиве;
//age — возраст для поиска;
Wood* WoodSearch(Wood* Head, double lifespan)
<
Wood* p = Head; // указывает на начало
while (p != NULL ) //Пока не конец списка
<
if (p->lifespan == lifespan) //Если элемент найден, то
break ; //прерываем цикл
p = p->Next; //Переход к следующему элемент
>
return p;
>

//Функция удаления дерева по значению поля
void DeleteWood(Wood*& pbeg, Wood* pos)
<
//если список пуст или pos равен NULL
if (pbeg == NULL || pos == NULL )
return ; //выходим
//Если pos указывает
//на начало
if (pos == pbeg)
< //Пусть pbeg укажет на
//следующий элемент
pbeg = pbeg->Next;
//Освобождаем память,
//на которую указывает
//pos
delete pos;
>
else
<
Wood* prev = pbeg;
while (prev != NULL && prev->Next != pos)
prev = prev->Next;
if (prev != NULL )
<
prev->Next = pos->Next;
delete pos;
>
>
>

void FreeWood(Wood*& pbeg)
<
Wood* p;
while (pbeg != NULL )
<
p = pbeg;
pbeg = pbeg->Next;
delete p;
>
>

int main()
<
char name[maxSize] = <'\0'>;
char type[maxSize] = <'\0'>;
double MaximumHeight;
double lifespan;

Wood* Head = nullptr;
int n;

//Вводим число деревьев, которые будем хранить в массиве
cout << "Number of Wood = " ;
cin >> n;
//Вводим информацию о всех деревьях с помощью реализованной функции
for ( int i = 0; i < n; i++)
<
WoodInput(name, type, MaximumHeight, lifespan);
>

// удаление элемента
cout << " deleted Woods = " ;
cin >> lifespan;
DeleteWood(Head, WoodSearch(Head, lifespan)); // ЗДЕСЬ ОШИБКА
PrintWood(Head);