线性表是n个数据元素的有限序列,最常用的是链式表达
,通常也叫做线性链表或者链表
在链表中存储的数据元素也叫做结点
,一个结点存储的就是一条数据记录
。
每个结点的结构包括两个部分:
在链表的最后一个结点,通常会有个头指针用来指向第一个结点
对于链表的最后一个结点,由于在它之后没有下一个结点,因此它的指针是个空指针
假如:小明,小张,小李和小郑在排队卖鸡翅,但是排队就是讲究先来先买的原则,不能插队。小明再购买鸡翅付钱的时候突然没钱了,假设小明和小郑认识,小明需要找到小郑借钱来付上买鸡翅的钱。。。那么小明想要找到小郑,就需要先找到他的下一个结点,一看不是小郑,就继续下一个结点,直到找到为止。
小明是可以找到小郑的,但是小郑就无法找到小明了,也就是说单链表
反过来查找是不行的,也被称之为单向链表
。
为了弥补单向链表的不足
,我们可以对单向链表进行改造:
对于单向链表,把最后一个元素的指针指向第一个元素,就得到了
循环链表
。 这样小郑就可以查找他自己的next结点,就可以找到小明或者小李等。
由于单向链表一个结点只有指向下一个结点的指针,可以想象一下,是不是也可以修改成每个结点也指向上一个结点,是不是就可以找到自己上一个结点的数据了呢。
我们再增加一个指向上一个结点的指针,这样就得到了
双向链表
当然了,还有更好的办法,那就是把循环链表
和双向链表
进行结合
就得到了双向循环链表
。
不管是循环链表还是双向链表,还是双向循环链表,都是在单向链表的基础上加以改造得到的,改造后的链表在操作某种数据的时候可以提高一定的效率,所以单向链表是基础。
对数据的操作无非就是对数据的增删改查
。只是不同的结构有着不同的处理逻辑罢了。
小明、小张、小李、小郑在排着队取票
,突然来了一个老王,老王非常的着急,因为老王马上就要到火车发车的时间了,只好插队了,此时老王跟后面所有的排队的人都打了个招呼,然后大家也都同意他插队进去,那么老王就先去取票了,我们忽略打招呼的过程,重点放在如何插队
。
我们先不管如何插入到链表中的,先看图说话
。
老王如果想插队必定插入到小明的后面,因为老王在插队的过程中小明此时可能会正在取票呢。
那么插入老王后的数据就是:
整个插入操作也非常的简单,只需要让老王的next指向小张,然后小明再指向老王就ok了。
思考一下????
反过来操作可以吗?
让小明先指向老王
,老王的next指向小张
。
可以吗?
答案是不可以的,这样的话,小明先指向老王
之后,小张以及小张之后的数据会全部丢失的。不信你看:
代码如下:
newNode.next = head.next
head.next = newNode
12
老王要想取到票,还欠一点火候,欠什么呢?需要等待小明取完票,然后离开才可以的。
那么就需要小明离开这个链表,我们通常说删除小明这个结点。
删除操作也比较简单,只需要把前一个结点指向后面的后面的这个结点就ok了。
代码:(直接就可以忽略小明这个结点)
head.next=head.next.next;
1
查找操作我们通常会查两种,第一种是按照位置的序号,第二种是按照值来查找。
例如:
在链表中的查找功能是比较弱的,对于链表中的查找,唯一的办法就是一个挨着一个的遍历去对比,对比较着去查找。
时间复杂度也就是O(N)。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null)
return head;
//定义三个指针暂存后面的或者前面的结点,防止丢失。
ListNode curr,prev,next;
curr=head;
prev=next=null;
while(curr!=null){
next = curr.next;
curr.next = prev;
prev=curr;
curr=next;
}
return prev;
}
}
1234567891011121314151617181920212223242526272829
如果不明白,可以自己画图来试试。
难度简单256收藏分享切换为英文关注反馈
给定一个带有头结点 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
12345
示例 2:
输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
123
提示:
1
和 100
之间。https://leetcode-cn.com/problems/middle-of-the-linked-list/
思路很简单,就是利用两个指针来完成,一个走的比较快的,一个走的比较慢的。
每次快的走2个(next.next),每次慢的走1个节点(next)。
当快等于null时(next.next=null时),停止;
当快的next不为空时,返回慢的next节点。
当快的next为空时,返回慢的当前节点。
//找出链表中间节点
static public ListNode middleNode(ListNode head) {
if(head==null)
return head;
ListNode fast,//快
slow;//慢
fast=slow=head;
while (fast!=null && fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
}
if(fast.next!=null)
return slow.next;
return slow;
}
12345678910111213141516171819
难度简单738收藏分享切换为英文关注反馈
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
123
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
123
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
123
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
此题也是可以利用快慢指针来完成的,同样,快指针一次走两步,慢指针一次走一步,如果有环的话,快和慢两个指针早晚会相遇的。那么如果快指针的val等于慢指针的val那么直接返回true即可。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null)
return false;
ListNode fast,slow;
fast=slow=head;
while (fast!=null && fast.next!=null && fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast.val==slow.val)
return true;
}
return false;
}
}
12345678910111213141516171819202122232425262728
链表对数据的存储方式是按照顺序的存储。