原创

剑指Offer面试题:4.从尾到头打印链表

一、题目:从尾到头打印链表

题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。

  到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”,我们可以用栈实现这种顺序。

二、解题思路

Stack

  每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,此时输出的结点的顺序已经反转过来了。

三、解决问题

3.1 代码实现

  这里使用的是自定义实现的链表类,其节点定义如下:

    public class Node<T>
    {
        // 数据域
        public T Item { get; set; }
        // 指针域
        public Node<T> Next { get; set; }

        public Node()
        {
        }

        public Node(T item)
        {
            this.Item = item;
        }
    }

  这里的自定义的单链表的实现请参考:《数据结构基础温故-1.线性表(中)

  (1)基于栈的循环版本

    public static void PrintListReversinglyIteratively(Node<int> head)
    {
        Stack<Node<int>> stackNodes = new Stack<Node<int>>();
        Node<int> node = head;
        // 单链表元素依次入栈
        while (node != null)
        {
            stackNodes.Push(node);
            node = node.Next;
        }
        // 栈中的单链表元素依次出栈
        while (stackNodes.Count > 0)
        {
            Node<int> top = stackNodes.Pop();
            Console.Write("{0}", top.Item);
        }
    }

  (2)递归版本

    public static void PrintListReversinglyRecursively(Node<int> head)
    {
        if (head != null)
        {
            if (head.Next != null)
            {
                PrintListReversinglyRecursively(head.Next);
            }

            Console.Write("{0}", head.Item);
        }
    }

  两个版本的对比:上面的基于递归的代码看起来很简洁,但有个问题:当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出显式用栈基于循环实现的代码的鲁棒性要好一些

3.2 单元测试

  (1)单元测试主入口

    // 测试主入口
    static void PrintTestPortal(Node<int> head)
    {
        Console.WriteLine("-------Begin--------");
        NormalPrint(head);
        Console.WriteLine();
        PrintListReversinglyIteratively(head);
        Console.WriteLine();
        PrintListReversinglyRecursively(head);
        Console.WriteLine("\n-------End--------");
    }
    // 辅助方法:正序打印链表
    static void NormalPrint(Node<int> head)
    {
        Node<int> temp = head;
        while(temp != null)
        {
            Console.Write("{0}",temp.Item);
            temp = temp.Next;
        }
    }

  在测试入口中,我们首先正序打印链表,然后使用循环版从尾到头打印链表,最后使用递归版从尾到头打印链表。

  (2)正常的多元素链表

    // 1->2->3->4->5
    static void PrintTest1()
    {
        Console.WriteLine("TestCase1:");
        SingleLinkedList<int> linkedList = new SingleLinkedList<int>();
        linkedList.Add(1);
        linkedList.Add(2);
        linkedList.Add(3);
        linkedList.Add(4);
        linkedList.Add(5);

        PrintTestPortal(linkedList.Head);
    }

  (3)只有一个节点的链表

    // 只有一个节点的链表
    static void PrintTest2()
    {
        Console.WriteLine("TestCase2:");
        SingleLinkedList<int> linkedList = new SingleLinkedList<int>();
        linkedList.Add(1);

        PrintTestPortal(linkedList.Head);
    }

  (4)鲁棒性测试:NULL

    // 空链表
    static void PrintTest3()
    {
        Console.WriteLine("TestCase3:");

        PrintTestPortal(null);
    } 

  测试结果如下图所示:

 

正文到此结束
本文目录