4

当我说不使用任何指针时，我的意思是我们仍然使用“下一个”指针字段来遍历列表，但在反转链表时不会更改它们。

据我所知，似乎有办法做到这一点：

  • 一种方法是在不更改指针本身的情况下反转节点中的数据。
  • 第二个是创建一个与原始链表相反的新链表。

如果有人可以帮助我了解如何使用第一种方法，我将不胜感激。也欢迎其他方法。

4

6 回答 6

5

今天在工作中，我一直在试图理解这个问题。我发现您的限制有些莫名其妙，因此“您尝试过魔法吗？” 评论。最终我越过了障碍...

它可能有助于可视化问题。让我们从 Julio Moreno 代码中的想法开始，稍微简化一下：遍历列表并将每个节点数据与尾部数据交换。

A B C D E
E B C D A
E A C D B
E A B D C
E A B C D

E D B C A
E D A C B
E D A B C

E D C B A

（在工作中我断定这个过程不会成功，但现在我有更多时间可以看到它了）。如果我们再仔细看看他的函数，我们可以看到除此之外，它还可以递归地工作。我并不热衷于可视化从 for 循环调用的递归函数。这个过程显然不会因效率而赢得任何奖励。

那么让我们看看如果我们不想限制自己不修改节点位置，我们可以做什么：

A B C D E
  B C D E A
    C D E B A
      D E C B A
        E D C B A

这里我们取尾节点 E，并记住它。我们现在将节点 A 插入到 E 之后，然后将 B 插入到 E 之后但 A 之前，逐步遍历整个列表，立即插入 E 之后，直到 E 成为列表的第一个节点（头）。它有效，但我们不允许这样做。

让我们假装更进一步，假设它是一个双向链表，我们维护两个指针，一个在列表的开头，一个在结尾，我们交换两者的数据，然后增加一个，减少另一个， 分别。

A B C D E
E B C D A
E D C B A

完成了！

那么我们如何使用单链表来做到这一点呢？我们需要知道什么？我们如何在退后一步的同时又向前迈进？

让我们从如何通过遍历整个列表来获取最后一个节点开始。

A B C D E F G H

并交换它们：

H B C D E F G A

然后如果我们记得我们交换数据的两个节点，我们可以从 B 开始并逐步前进，直到 node->next 指向现在保存数据 A 的节点。

B C D E F G

并交换它们：

G C D E F B
  F D E C
    E D

然而，我仍然对重复遍历列表的想法感到不舒服——即使步进的范围在每次迭代过程中都会缩小。如果我们有一个 LIFO（后进先出）或堆栈怎么办？

A B C D E F G H
  B C D E F G H ... A
    C D E F G H ... B
      D E F G H ... C
        E F G H ... D
          F G H ... E
            G H ... F
              H ... G...F...E...D...C...B...A

但这是辅助数据存储，我们不允许这样做，但不难看出如何使用递归函数调用和链表来实现 LIFO。那么我们如何通过递归函数调用和链表来前进和后退呢？我们不需要额外的参数吗？当我们到达列表的末尾时，我们仍然需要知道它是如何开始的。

A B C D E F G H
A,B             ^ return 0
  A,C           ^ return 0
    A,D         ^ return 0
      A,E       ^ swap D E done, return 0
        A,F     ^ swap C F return D
          A,G   ^ swap B G return C
            A,H ^ swap A H return B

我还没有实际测试过这一点来证明它，所以它可能是错误的。我现在就去测试它，如果需要可以发布代码。希望我不必编辑这篇文章就说它不起作用；-)

编辑：可以确认它有效。

static lnode* list_private_reverse(lnode* list, lnode* node)
{
    lnode* next = node->next;

    if (next)
    {
        lnode* swap = list_private_reverse(list, next);

        if (swap)
        {
            int c = swap->c;

            swap->c = node->c;
            node->c = c;

            if (swap->next == node || swap->next->next == node)
                return 0;

            return swap->next;
        }
        return 0;
    }
    else
    {
        int c = node->c;
        node->c = list->c;
        list->c = c;
    }

    return list->next;
}

lnode* list_reverse(lnode* list)
{
    list_private_reverse(list, list);
    return list;
}

list_private_reverse仅调用列表中元素的次数。

于 2013-07-24T16:38:06.693 回答
4

这个问题与任何其他反转问题没有太大区别。一种解决方案是遍历列表，并将每个数据项放入一个数组中。然后，再次遍历列表，但从数组的末尾开始，并以相反的顺序用数组中的值覆盖列表数据。

for (n in list) arr[i++] = n->data
for (n in list) n->data = arr[--i]

如果您不允许存储任何内容，那么递归也将退出，因为它充当辅助数组来存储您的反向列表。然后一个愚蠢的解决方案是实现对列表的随机访问接口：

Node * nth_list_item (Node *list, int n);

它返回列表的第一n项。然后，您可以使用此接口反转列表，该接口可以像访问数组一样访问它（当然会有时间损失）。反转不再需要 O(n) 时间，但现在是 O(n 2 )。

如果递归没问题，那么为了满足“不存储元素”要求的精神，您需要递归遍历列表，然后在展开时反转列表。这可以通过允许递归调用的另一个参数来提供在递归调用从末尾展开时遍历列表开头所需的指针来实现。此实现在每个递归调用中不使用额外的局部变量，仅使用参数中提供的变量。

void swap_left (node *a, node *b, int tmp) {
    a->data = b->data;
    b->data = tmp;
}

void reverse_recursively (node *cur, node **tail) {
    if (cur) {
        reverse_recursively(cur->next, tail);
        if (*tail) {
            swap_left(cur, *tail, cur->data);
            if (cur != *tail) *tail = (*tail)->next;
            if (cur == *tail) *tail = 0;
        }
    }
}

void reverse (node *list) {
    reverse_recursively(list, &list);
}

如果允许我们在使用递归时侵犯“不存储元素”要求的精神，那么就有一个更直接（但更占用空间）的解决方案。基本上，可以在递归遍历它的同时创建反向链表的副本。当到达它的末尾时，可以再次遍历列表，从反向副本中复制元素。

#define make_node(n, d) (node){ n, d }

void reverse_recursively (node *list, node *cur, node copy) {
    if (!cur) {
        for (cur = © cur; cur = cur->next, list = list->next) {
            list->data = cur->data;
        }
        return;
    }
    reverse_recursively(list, cur->next, make_node(&copy, cur->data));
}

void reverse (node *list) {
    if (list == 0) return;
    reverse_recursively(list, list->next, make_node(0, list->data));
}
于 2013-07-23T21:17:02.610 回答
0

实现一个堆栈并使用它来反转链表。堆栈是先进后出数据结构 (FILO)。在第一次迭代中将链表的内容压入堆栈，然后在第二次迭代中将它们弹回列表中。

一旦你实现了一个堆栈，它就可以很好地解决大部分的反转问题。

当然，您会使用更多空间，这意味着它不是原位的。

于 2013-09-12T13:36:45.987 回答
0

@ames Morris——解释得很好。但是你和我的代码有什么区别......

最多使用 2 个指针...

Node* reverseLL (Node *curr, Node *prev)
{
  Node *nxt = NULL;
  if (curr)
  {
    nxt = curr->next;
    curr->next = prev;
    curr = reverseLL (nxt, curr);
  }
  else
    return prev;
}

void reverseList (Node **head)
{
  Node *curr = *head;
  Node *prev = NULL;
  curr = reverseLL (curr, prev);
  *head = curr;
}
于 2013-09-11T10:11:28.907 回答
0

像这样的东西会起作用，第一个函数实际上并没有切换（抱歉名称令人困惑），它的工作原理很像插入算法，它获取列表的最后一个元素并将其插入“当前”位置。我严重怀疑这个算法的效率：

    typedef struct node node;
    struct node {
        node *next;
        void *value;
    };
    typedef node linked_list;

    node *switch_with_end(node *c)
    {
        if (c->next) {
            node *t = switch_with_end(c->next);
            void *temp = t->value;
            t->value = c->value;
            c->value = temp;
        }
        return c;
    }

    void reverse_list(linked_list *l)
    {
        node *c;
        for (c = l; c->next; c = c->next)
            switch_with_end(c);
    }
于 2013-07-23T22:16:01.853 回答
0 
 //Reversal of linked list without using pointers.
void reverseList(ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;
    reverseList(head->next);
    //save the current value
    int val = head->val;
    ListNode *temp = head;
    // shift all the values to the left
    while(temp->next != NULL)
    {
        temp->val = temp->next->val;
        temp = temp->next;
    }
    // assign the save value at the end of the list
    temp->val = val;
    return;
}
于 2019-04-12T18:34:11.583 回答