1.3.30

1.3.30 #

解答 #

书中给出了代码，这里说一下递归的实现。

如果说一个链表除了第一个结点剩下的都已经反转了，那么我们就只要把该结点插入到最后就行了（也就是原先的第二个结点之后）。

像这样：

代码 #

var first = new Node<string>();
var second = new Node<string>();
var third = new Node<string>();
var fourth = new Node<string>();

first.Item = "first";
second.Item = "second";
third.Item = "third";
fourth.Item = "fourth";

first.Next = second;
second.Next = third;
third.Next = fourth;
fourth.Next = null;

var current = first;
while (current != null)
{
    Console.Write(current.Item + " ");
    current = current.Next;
}

first = Reverse(first);
Console.WriteLine();

current = first;
while (current != null)
{
    Console.Write(current.Item + " ");
    current = current.Next;
}

// 使用书中的递归方式实现
static Node<TItem> Reverse<TItem>(Node<TItem> first)
{
    if (first == null)
        return null;
    if (first.Next == null)
        return first;
    var second = first.Next;
    var rest = Reverse(second);
    second.Next = first;
    first.Next = null;
    return rest;
}

另请参阅 #

Generics 库