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

Question

Мне было бы интересно, если бы существовала какая-то логика для обратного связанного списка, используя только два указателя.

Следующее используется для обращения к единому связанному списку с использованием трех указателей, а именно 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;
}

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

Answer 1

Есть альтернатива? Нет, это так просто, как есть, и нет принципиально иного способа сделать это. Этот алгоритм уже 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;
}

Answer 2

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

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

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

#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 по своему желанию.

Answer 3

#include <stddef.h>

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

Node * reverse(Node *cur) {
    Node *prev = NULL;
    while (cur) {
        Node *temp = cur;
        cur = cur->next; // advance cur
        temp->next = prev;
        prev = temp; // advance prev
    }
    return prev;
}

Answer 4

Вот код обратный односвязный список в C .

А вот это наклеено ниже:

// reverse.c

#include <stdio.h>
#include <assert.h>

typedef struct node Node;
struct node {
    int data;
    Node *next;
};

void spec_reverse();
Node *reverse(Node *head);

int main()
{
    spec_reverse();
    return 0;
}

void print(Node *head) {
    while (head) {
        printf("[%d]->", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void spec_reverse() {
    // Create a linked list.
    // [0]->[1]->[2]->NULL
    Node node2 = {2, NULL};
    Node node1 = {1, &node2};
    Node node0 = {0, &node1};
    Node *head = &node0;

    print(head);
    head = reverse(head);
    print(head);

    assert(head == &node2);
    assert(head->next == &node1);
    assert(head->next->next == &node0);

    printf("Passed!");
}

// Step 1:
//
// prev head  next
//   |    |    |
//   v    v    v
// NULL  [0]->[1]->[2]->NULL
//
// Step 2:
//
//      prev head  next
//        |    |    |
//        v    v    v
// NULL<-[0]  [1]->[2]->NULL
//
Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *next;

    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;
}

Answer 5

Роберт Седжвик, " Алгоритмы на C ", Addison-Wesley, 3rd Edition, 1997, [Section 3.4]

В случае, если это не циклический список, следовательно, NULL является последней ссылкой.

<code>typedef struct node* link;</p>

<p>struct node{
    int item;
    link next;
};</p>

<p>/* you send the existing list to reverse() and returns the reversed one */</p>

<p>link reverse(link x){
    link t, y = x, r = NULL;
    while(y != NULL){
        t = y->next;
        y-> next = r;
        r = y;
        y = t;
    }
    return r;
}

Answer 6

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

Вам нужно два указателя:

первый указатель для выбора первого узла. второй указатель для выбора второго узла.

Обработка:

указатель перемещения по дорожке

Укажите второй узел на первый узел

Переместить первый указатель на один шаг, назначив второй указатель одному

Переместить второй указатель на один шаг, назначив указатель дорожки второму

Node* reverselist( )
{
   Node *first = NULL;  // To keep first node
   Node *second = head; // To keep second node
   Node *track =  head; // Track the list

    while(track!=NULL)
    {
      track = track->next; // track point to next node;
      second->next = first; // second node point to first
      first = second; // move first node to next
      second = track; // move second node to next
    }

    track = first;

    return track;

}

Answer 7

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

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

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

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

root = reverse(root, NULL);

Answer 8

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

a = a xor b
b = a xor b
a = a xor b

Самый быстрый способ - записать его в одну строку

a = a ^ b ^ (b=a)

Аналогично,

с использованием двух свопов

swap(a,b)
swap(b,c)

решение с использованием xor

a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c

решение в одну строку

c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a)

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

typedef struct List
{
 int info;
 struct List *next;
}List;


List* reverseList(List *head)
{
 p=head;
 q=p->next;
 p->next=NULL;
 while(q)
 {
    q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
 }
 head = p;
 return head;
}  

Answer 9

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

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

Answer 10

Как насчет более читабельного:

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);
}