如何仅使用两个指针来反转单链表？ [英] How to reverse a singly linked list using only two pointers?

问题描述

我会想知道是否存在一些逻辑来使用两个指针来反转链表。

I would be wondered if there exists some logic to reverse the linked list using only two pointers.

以下内容用于使用三个指针来反转单个链表即p，q，r：

The following is used to reverse the single linked list using three pointers namely 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;
    }
    q = first;
}

是否有其他替代方法可以反转链表？在时间复杂度方面，反转单链表的最佳逻辑是什么？

Is there any other alternate to reverse the linked list? what would be the best logic to reverse a singly linked list, in terms of time complexity?

推荐答案

我讨厌成为承载者的坏消息，但我不认为你的三指针解决方案实际上是有效的。当我在以下测试工具中使用它时，根据以下输出将列表减少到一个节点：

I hate to be the bearer of bad news but I don't think your three-pointer solution actually works. When I used it in the following test harness, the list was reduced to one node, as per the following output:

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

你不会得到比你的解决方案更好的时间复杂度，因为它是O（n），你必须访问每个节点来改变指针，但是你可以很容易地做一个只有两个额外的指针的解决方案，如下所示代码：

You won't get better time complexity than your solution since it's O(n) and you have to visit every node to change the pointers, but you can do a solution with only two extra pointers quite easily, as shown in the following code:

#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
==========

我认为是你以后，实际上可以这样做，因为一旦你加载了 / code>到遍历列表的指针中，您可以随意重新使用第一个。

which I think is what you were after. It can actually do this since, once you've loaded up first into the pointer traversing the list, you can re-use first at will.

这篇关于如何仅使用两个指针来反转单链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！