面試題【從尾到頭列印鏈表】精妙解法

題目描述

輸入一個鏈表，按鏈表值從尾到頭的順序返回一個List。

解題思路

輸入一個鏈表，從尾到頭輸出，正常的遍歷都是從頭到尾輸出，而這裡需要從尾到頭輸出，那麼就是“先進後出”，也就是棧的功能。

代碼實現

棧的方式實現

public static List<int> PrintForStack(ListNode nodes)
{
    Stack<ListNode> listNodes = new Stack<ListNode>();
    ListNode node = nodes;
    while (node != null)
    {
        listNodes.Push(node);
        node = node.next;
    }

    List<int> list = new List<int>();
    foreach (var item in listNodes) {
        list.Add(item.item);
    }
    return list;
}

遞歸的方式實現

public static List<int> PrintForRecursion(ListNode node) {
    List<int> listNodes = new List<int>();
    PrintForRecursion(node, listNodes);
    return listNodes;
}

private static void PrintForRecursion(ListNode node, List<int> list)
{
    if (node != null) {
        if (node.next != null) {
            PrintForRecursion(node.next, list);
        }
        list.Add(node.item);
    }
}

想入非非：擴展思維，發揮想象

目的：

1. 熟悉鏈表

2.熟悉棧（先進後出）

3.熟悉遞歸

擴展：

1.輸入一個鏈表，返回一個倒過來的鏈表

public static ListNode PrintForReverse(ListNode nodes)
{
    Stack<ListNode> listNodes = new Stack<ListNode>();
    ListNode node = nodes;
    while (node != null)
    {
        listNodes.Push(node);
        node = node.next;
    }

    ListNode reverseNode = listNodes.Pop();
    var temp = reverseNode;
    foreach (var item in listNodes)
    {
        item.next = null;
        temp.next = item;
        temp = item;
    }
    return reverseNode;
}

2.生成一個鏈表

public static ListNode CreateNodeList(int length)
{
    ListNode listNode = new ListNode(0);
    var temp = listNode;
    for (int i = 1; i < length; i++)
    {
        temp = nextList(temp, i);
    }

    return listNode;

    //下一個
    ListNode nextList(ListNode node, int value)
    {
        while (node.next != null)
        {
            node = node.next;
        }
        var next = new ListNode(value);
        node.next = next;
        return next;
    }
}

測試

[Fact]
public void TestList()
{
    ListNode listNode = Coding003.CreateNodeList(10);
    List<int> test = Coding003.PrintForStack(listNode);
    for (int i = 0; i < 10; i++)
    {
        Assert.Equal(i, test[9 - i]);
    }

    List<int> test2 = Coding003.PrintForRecursion(listNode);
    for (int i = 0; i < 10; i++)
    {
        Assert.Equal(i, test2[9 - i]);
    }
}

[Fact]
public void Test()
{
    ListNode listNode = Coding003.CreateNodeList(10);
    string o = JsonConvert.SerializeObject(listNode);

    List<int> test = Coding003.PrintForStack(listNode);
    string t = JsonConvert.SerializeObject(test);

    List<int> test2 = Coding003.PrintForRecursion(listNode);
    string t2 = JsonConvert.SerializeObject(test2);

    ListNode test3 = Coding003.PrintForReverse(Coding003.PrintForReverse(listNode));
    string t3 = JsonConvert.SerializeObject(test3);

    Assert.Equal(test, test2);
    Assert.Equal(o, t3);
}

面試題【字元串替換空格】

面試題【二維數組中的查找】