Как инвертировать отдельно связанный список с помощью только двух указателей?

Интересно, существует ли там некоторая логика для инвертирования отдельно-связанного-списка с помощью только двух указателей.

Следующее используется для инвертирования единственного связанного списка с помощью трехочковых а именно, p, q, r:

struct node {
    int data;
    struct node *link;
};

void reverse() {
    struct node *p = first,
                *q = NULL,
                *r;

    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

Там кто-либо другой является альтернативным для инвертирования связанного списка? Какова была бы лучшая логика для инвертирования отдельно связанного списка, с точки зрения временной сложности?

109
задан Jonathan Leffler 1 October 2019 в 20:48
поделиться

8 ответов

Есть альтернатива? Нет, это настолько просто, насколько возможно, и принципиально другого способа сделать это не существует. Для этого алгоритма уже используется время O (n), и вы не можете работать быстрее этого, поскольку вы должны изменить каждый узел.

Похоже, ваш код находится на правильном пути, но он не совсем работает в форме над. Вот рабочая версия:

#include <stdio.h>

typedef struct Node {
  char data;
  struct Node* next;
} Node;

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}
131
ответ дан 24 November 2019 в 03:22
поделиться

Просто для удовольствия (хотя оптимизация хвостовой рекурсии должна остановить поглощение всего стека):


Node* reverse (Node *root, Node *end) {

    Node *next = root->next;
    root->next = end;

    return (next ? reverse(next, root) : root);
}

root = reverse(root, NULL);
3
ответ дан 24 November 2019 в 03:22
поделиться

Как насчет более удобочитаемого:


Node *pop (Node **root)
{
    Node *popped = *root;

    if (*root) {
        *root = (*root)->next;
    }

    return (popped);
}

void push (Node **root, Node *new_node)
{
    new_node->next = *root;
    *root = new_node;
}


Node *reverse (Node *root)
{
    Node *new_root = NULL;
    Node *next;

    while ((next = pop(&root))) {
        push (&new_root, next);
    }

    return (new_root);
}
2
ответ дан 24 November 2019 в 03:22
поделиться

Да. Я уверен, что вы можете сделать это так же, как , вы можете поменять местами два числа без использования третьего . Просто приведите указатели к int / long и несколько раз выполните операцию XOR. Это один из тех приемов C, которые создают забавный вопрос, но не имеют практического значения.

Можете ли вы уменьшить сложность O (n)? Нет, не совсем. Просто используйте двусвязный список, если вы думаете, что вам понадобится обратный порядок.

3
ответ дан 24 November 2019 в 03:22
поделиться

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

==========
4
3
2
1
0
==========
4
==========

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

#include <stdio.h>

// The list element type and head.

struct node { 
    int data;
    struct node *link;
};
static struct node *first = NULL;

// A reverse function which uses only two extra pointers.

void reverse() {
    // curNode traverses the list, first is reset to empty list.
    struct node *curNode = first, *nxtNode;
    first = NULL;

    // Until no more in list, insert current before first and advance.
    while (curNode != NULL) {
        // Need to save next node since we're changing the current.
        nxtNode = curNode->link;

        // Insert at start of new list.
        curNode->link = first;
        first = curNode;

        // Advance to next.
        curNode = nxtNode;
    }
}

// Code to dump the current list.

static void dumpNodes() {
    struct node *curNode = first;
    printf ("==========\n");
    while (curNode != NULL) {
        printf ("%d\n", curNode->data);
        curNode = curNode->link;
    }
}

// Test harness main program.

int main (void) {
    int i;
    struct node *newnode;

    // Create list (using actually the same insert-before-first
    // that is used in reverse function.

    for (i = 0; i < 5; i++) {
        newnode = malloc (sizeof (struct node));
        newnode->data = i;
        newnode->link = first;
        first = newnode;
    }

    // Dump list, reverse it, then dump again.

    dumpNodes();
    reverse();
    dumpNodes();
    printf ("==========\n");

    return 0;
}

Этот код выводит:

==========
4
3
2
1
0
==========
0
1
2
3
4
==========

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

44
ответ дан 24 November 2019 в 03:22
поделиться

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

0
ответ дан 24 November 2019 в 03:22
поделиться

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

0
ответ дан 24 November 2019 в 03:22
поделиться

Решение с использованием 1 переменной (только p ):

typedef unsigned long AddressType;

#define A (*( AddressType* )&p )
#define B (*( AddressType* )&first->link->link )
#define C (*( AddressType* )&first->link )

/* Reversing linked list */
p = first;

while( first->link )
{
    A = A + B + C;
    B = A - B - C;
    A = A - B;
    C = A - C;
    A = A - C;
}

first = p;
-1
ответ дан 24 November 2019 в 03:22
поделиться
Другие вопросы по тегам:

Похожие вопросы: