单向链表逆序排列（单向链表逆序排列怎么排）



链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。

想必大家对数组都非常熟悉，数组在存储空间（内存）上是连续的。因此，我们可以根据偏移量轻易的找到数组中的数据。但数组最大的问题是大小是固定的，很多场景是无法预判需要的空间大小的。

链表也是一种线性数据结构，但它最大的优势是可以动态的调整大小。这样，我们再也不用担心应该分配多少空间了。

链表是一种物理存储单元上非连续、非顺序的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的

链表在日常开发中通常通过数据结构和指针的方式实现，其中包含一个本数据结构的next指针，用于指向下一个元素，这样指下去，就形成了一个单向链表。如下是数据结构的定义：

为了便于链表的管理和使用，我们在实际定义的时候通常还会定义个专门的链表头，链表头的定义如下：

通过增加一个链表头可以方便链表的管理，同时通过增加的元数据可以很方便的得到一些链表的信息，从而提高效率。这样，整个链表的结构大概如图1所示。

图1 单向链表示意图

单向链表最主要的接口就是初始化、插入元素和删除元素等操作了。当然，为了方便使用，还有返回链表头元素，链表尾元素和链表大小等等。我们这里先看一下几个主要的函数接口。

下面我们给出插入操作的代码实现，其它操作类似，也比较简单，这里就不罗列代码了。具体可以参考本文的配套github库。

关于单向链表的面试题很多，我们这里尽量的都收集过来。目前有些复杂的没有答案，但我们后续会陆续写文章将答案收集起来。

这个题目是比较简单的，基本做法就是对单向链表进行遍历。在进行遍历的时候有一个计数的变量，每遍历一个节点，计数增1，直到完成链表的遍历。

将链表中的节点指向反过来，比如原来的指向为1->2->3->4->5，那么反转后为5->4->3->2->1。链表反转其实是调整节点的next指针的指向。具体如图所示。

图2 链表反转示意图

给定一个有序的链表，删除所有重复的元素，保证每个元素在链表中只出现一次。

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。也就是你仅知道要求被删除的节点。

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

题目
删除链表中等于给定值 val 的所有节点。
示例

约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

给一个链表和整数k，将后k个节点移到链表头。

题目：给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数。

题目 ： 按某个给定值将链表划分为左边小于这个值，右边大于这个值的新链表 如一个链表 为 1 -> 4 -> 5 -> 2 给定一个数 3 则划分后的链表为 1-> 2 -> 4 -> 5

题目 给定一个单链表L： L0→L1→…→Ln-1→Ln, 重新排列后为 L0→Ln→L1→Ln-1→L2→Ln-2→… 要求必须在不改变节点值的情况下进行原地操作。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/59458.html