面试官问数据分析具体怎么回答（面试官你都工作3年了）

文|洪生鹏

面试时，基本的数据结构经常会遇到。

最近有个读者分享了他一次扎心求职经历，分享给大家，之所以说扎心了，是因为他对面试官提出的基本问题都没有回答个所以然。

小唐是一名java程序员，工作3年了，平时工作内容都倾向业务方面的，对于数据结构基础知识接触得比较少。

最近到一家互联网公司面试，面试官问了他这样一个问题：

如何对单链表的数据进行反转？

要是说对字符串进行反转，小唐倒是能回答，可单链表，小唐平时工作很少接触，只记得是数据结构方面的知识点，这些在大学时上课倒是经常接触，现在都忘记了差不多了。

面试官见小唐没有作答，于是说，你都工作了3年了，怎么连数据结构栈最基本的都没掌握啊。

小唐被面试官这么一说，特别不好意思，确实不应该，类似这样基本的数据结构，哪怕平时工作中没有应用到，也是需要掌握才行，毕竟程序开发离不开数据结构。

那么什么是单链表呢，我们不妨来对这个知识点简单回顾下。

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表的反转，有时候我们想对一组数据进行反转，比如：1—>2—>3—>4 反转成：4—>3—>2—>1

我们可以采用下面两种方式：

我们可以先定义个Node节点。

public class Node { private int data; private Node next; public Node(int data) { this.data = data; next = null; } public void setNext(Node next) { this.next = next; } public Node getNext() { return next; } public Node addNode(Node node) { next = node; return node; } @Override public String toString() { return "Node{" "data=" data ", next=" next '}'; } }

1、利用栈先进后出的特性

/** * 栈的特性，先进后出，实现单链表的反转 * @param head * @return */ public static Node reverse(Node head) { if (head == null || head.next == null) { return head; } Stack<Node> stack = new Stack<>(); while (head != null) { stack.push(head); head = head.getNext(); } head = stack.pop(); //记录当前节点位置 Node cur = head; while (!stack.isEmpty()) { Node node = stack.pop(); node.next = null; cur.next = node; cur = node; } return head; }

public class NodeReverse { public static void main(String[] args) { Node head = new Node(1); head.addNode(new Node(2)).addNode(new Node(3)).addNode(new Node(4)); System.out.println("栈的特性，先进后出，实现单链表的反转"); System.out.println("反转前:" head); Node reverse = Node.reverse(head); System.out.println("反转后:" reverse); } }

栈的特性，先进后出，实现单链表的反转

反转前:

Node{data=1, next=Node{data=2, next=Node{data=3, next=Node{data=4, next=null}}}}

反转后:

Node{data=4, next=Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}}

2、采用递归的方式实现单链表的反转

/** * 递归方式实现单链表的反转 * @param head * @return */ public static Node recursionReverse(Node head) { if (head == null || head.next == null) { return head; } Node prev = recursionReverse(head.next); head.next.next = head; head.next = null; return prev; }

public class NodeReverse { public static void main(String[] args) { Node node = new Node(1); node.addNode(new Node(2)).addNode(new Node(3)).addNode(new Node(4)); System.out.println("递归方式实现单链表的反转"); System.out.println("反转前:" node); Node recursion = Node.recursionReverse(node); System.out.println("反转后:" recursion); } }

递归方式实现单链表的反转

反转前:

Node{data=1, next=Node{data=2, next=Node{data=3, next=Node{data=4, next=null}}}}

反转后:

Node{data=4, next=Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}}

个人认为，关于数据结构还是挺重要，尤其是基础类，更加要重视。

由于笔者水平有限，文中纰漏之处在所难免，权当抛砖引玉，不妥之处，请大家批评指正。

关于单链表反转的，不知你有没有更好的方法，欢迎交流！

【END】

作者：洪生鹏 ， 自由职业者，白天搬砖，晚上摆地摊。

,