反向单链列表 [英] Reverse a single chained List

问题描述

我希望我使用正确的术语.我做了一个单链列表.

I hope I am using the right terminology. I have made a single-chained list.

class MyStack
{
    public Node Initial { get; set; }

    public MyStack()
    {
        Initial = null;
    }

    public void Push(int data)
    {
        var node = new Node { Data = data, Next = Initial };
        Initial = node;
    }

    public int Pop()
    {
        int res = Initial.Data;
        Initial = Initial.Next;
        return res;
    }

    public int Sum()
    {
        int sum = 0;
        Node currentNode = Initial;
        while (currentNode != null)
        {
            sum += currentNode.Data;
            currentNode = currentNode.Next;
        }
        return sum;
    }
    public int Count()
    {
        int count = 0;
        Node currentNode = Initial;
        while (currentNode != null)
        {
            count++;
            currentNode = currentNode.Next;
        }
        return count;
    }

    public void PrintAll()
    {     
        Node currentNode = Initial;
        while(currentNode != null)
        {
            Console.WriteLine("tmp.Data = " + currentNode.Data);
            currentNode = currentNode.Next;
        }
    }
}
public class Node
{
    public int Data;
    public Node Next;
}

意思是你可以做这样的事情:

Meaning you can do something like this:

    var s = new MyStack();
    s.Push(5);
    s.Push(3);
    s.Push(7);
    s.PrintAll();
    Console.WriteLine("Sum: " + s.Sum());
    Console.WriteLine("Count: " + s.Count());

现在，我想尝试做一个Reverse方法.这似乎可行:

Now, I want to try and make a Reverse method. This seems to be working:

public void Reverse()
{
    Node predesesor, location;
    location = Initial;
    predesesor = null;
    while(Initial != null)
    {
        Initial = Initial.Next;
        location.Next = predesesor;
        predesesor = location;
        location = Initial;
    }
    Initial = predesesor;
}

我几乎看不到它是如何工作的，并且很难维护.似乎更像是一种骇客.

I am hardly able to see how it works, and it will be tough to maintain. It seems more like a hack than anything else.

您能提供任何帮助吗?

推荐答案

在我看来，这似乎不是黑客，而且我看不到要维护的内容(它是否正确，您还会做什么?用它?).如果您想弄清楚它是如何工作的，请在纸上执行"每个步骤.绘制一个列表(例如1-> 3-> 5-> 7-> 9-> NULL)，标记出所有节点随时指向的位置，然后开始单步执行".

It doesn't seem like a hack to me and I don't see what's there to maintain (it is either correct or not, what else would you do with it?). If you want to figure out how it works, "execute" each step on paper. Draw a list (e.g 1 -> 3 -> 5 -> 7 -> 9 -> NULL), mark out where all Nodes point at any time and start "single-stepping".

我想不出更简洁的方法来反转单链表.您需要对下一个节点的引用(循环开始处的Initial)，然后才能反转当前节点和上一个节点之间的链接.否则，您将无法继续在原始列表中前进.

I couldn't think of a cleaner way to reverse a singly linked list. You need a reference to the next node (Initial at the beginning of the loop), before you can reverse the link between current node and previous node. You just won't be able to move on in the original list otherwise.

您可以做的是修复变量的拼写，并且可能不在循环本身中使用Initial(使用第三个变量，因此每个变量的作用更加清晰)，而仅将Initial设置为反向列表中的第一个Node最后.

What you could do is fix the spelling of the variables and perhaps not use Initial in the loop itself (use a third variable, so the role of each variable is clearer) and only set Initial to the first Node in the reversed list at the end.

总而言之:

public void Reverse() {
    Node current = Initial, previous = null;
    while (current) {
        Node next = current.Next;
        current.Next = previous;
        previous = current;
        current = next;
    }
    Initial = previous;
}

这篇关于反向单链列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！