面试题【二维数组中的查找】

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个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);
}

面试题【字符串替换空格】

面试题【二维数组中的查找】