反转单个链表

Question

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

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

意思是你可以这样做:

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

现在,我想尝试制作一个反向方法.这似乎有效:

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

我几乎无法看到它是如何工作的,而且很难维护.它似乎更像是一个黑客而不是其他任何东西.

你能提供任何帮助吗？

Answer 1

它对我来说似乎不是一个黑客,我不知道有什么需要维护(它是正确与否,你还会用它做什么？).如果你想弄清楚它是如何工作的,那就在纸上"执行"每一步.绘制一个列表(例如1 - > 3 - > 5 - > 7 - > 9 - > NULL),标记所有节点在任何时间指向的位置并开始"单步".

我想不出一个更简洁的方法来扭转单链表.在可以反转当前节点和上一个节点之间的链接之前,需要引用下一个节点(循环开始时的Initial).否则你将无法继续在原始列表中继续前进.

您可以做的是修复变量的拼写,也许不在循环中使用Initial(使用第三个变量,因此每个变量的角色更清晰)并且只将Initial设置为最后反向列表中的第一个Node .

总而言之:

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