数据域用来存储数据一个是指针域存放指向下一个节点的地址最后一个节点的指针域指向null空指针的意思。

链表的入口节点称为链表的头结点。

普通的单链表就是只给你一个指向链表头的指针head如果想访问其他元素就只能从head开始一个个向后找遍历链表最终会在访问尾结点之后如果继续访问就会返回null。

从上图看是不是觉得链表的存储方式有点像数组实际上链表的各节点在内存中的存储次序是混乱的它是通过指针域中的指针链接在内存中各个节点即每个节点中都有记录它所链接的节点的地址。

public

由于链表的各节点在内存中的存储次序是混乱的我们一般只知道它的头节点因此对于单链表不管进行什么操作一定是从头开始逐个向后访问直到null为止。

所以操作之后是否还能找到表头节点非常重要千万不要只顾当前位置而将标记表头的指针丢掉了。

/***

单链表的插入操作需要考虑三种情况首部插入、中部插入和尾部插入。

(2.1)

链表的首部插入非常简单我们只需要将待插入节点的指针域指向头节点然后更新头节点为待插入的节点即可。

/***

链表的中部插入会相对麻烦一点首先我们必须先遍历找到要插入的位置前驱节点然后在当前位置与前驱结点和后继结点进行连接。

为什么要找到前驱节点而不是待插入的位置呢这是由于链表的结构使然链表的遍历就如时间的流逝只能向后无法回溯。

如果我们遍历到待插入的位置若未记录前驱节点那么我们将无法再获取到前驱节点

/***

2.先令待插入的节点指向后继节点insertNode.next

head.next;//

为什么要先令待插入的节点指向后继节点再让前驱节点指向待插入的节点呢

这是由于每个节点都只有一个next即只能保存一份地址)倘若我们先令前驱节点指向待插入的节点那么原本前驱节点与后继节点之间的链接将会断开我们将丢失后续的节点。

(2.3)

尾部插入也是比较简单的我们只需要遍历到尾部节点再令尾部节点指向待插入的节点即可。

/***

与插入情况类似单链表的删除操作也需要考虑三种情况首部删除、中部删除和尾部删除。

(3.1)

删除头节点非常的简单只需要将当前头节点更新为当前头节点指针域所指向的地址即可。

/***

删除中间结点与插入类似也需要我们先找到待删除位置的前驱节点然后再将前驱节点的指针域改为后继节点指针域中所保存的地址。

/***

2.将前驱节点的指针域改为后继节点指针域中所保存的地址head.next

(3.3)

要删除尾部节点同样要找到尾部节点的前驱节点如果我们知道尾部节点的位置那么尾部节点的删除其实与中部节点的删除方法一致否则我们便需要通过cur.next.next

/***

2.将前驱节点的指针域改为后继节点指针域中所保存的地址head.next

head.next.next;

上面我们所讲解的链表都为单向链表即链表之间是单向连接的都由前一个节点指向后一个节点我们只能从某一个节点开始获取到它后面的节点而无法获取到它前面的节点。

双向链表顾名思义就是既可以向前也可以向后即链表之间是相互连接的我们即可从某一个节点开始获取到它后面的节点也可以获取到它前面的节点。

有两个指针的好处自然是移动元素更方便。

(2)

将还未插入节点结点的next指向第一个节点newDoubleNode.next

first;}//将新结点赋给first成为第一个结点first

newDoubleNode;

将还未插入节点结点的prev指向最后一个节点newDoubleNode.prev

last;}//

由于双向链表的特性中间插入节点方法不唯一总之都需要找到要插入位置的前驱节点或者后继节点。

(4)

{//若链表只有一个结点删除后链表为空将last指向nullif

(first.next

因为是头部删除则first.next将变成第一个结点其previous将变成nullfirst.next.prev

null;

{//如果链表只有一个结点则删除以后为空表,last指向nullif

(first.next

{//将上一个结点的next域指向nulllast.prev.next

null;

我们可以先将任意一个链表节点全部加入到集合中再遍历另一个链表比较该节点是否包含在集合中如果包含则代表它就是第一个公共子节点中止循环否则表示两个链表没有公共子节点。

public

如果两个链表有公共子节点那么它的第一个公共子节点以后的节点都应该是相同的我们可以先将两个链表的所有节点都分别压入栈中再依次出栈进行比较如果相等则继续出栈一直找到最晚出栈的那一组可以得知最后出栈的一对相等节点为第一个公共子节点。

public

3.当碰到第一对不相等的节点时可以得出上一对出栈的节点为第一个公共子节点if

(!aN.equals(bN))

由于第一个公共子节点可能距离两条链表的头节点不同距离我们可以先计算出两个链表的长度差令较长的链表先移动长度差距离使得两个链表的起始同步遍历位置与第一个公共子节点距离相同然后我们再同步遍历两条链表比较各个节点判断是否相等当碰到第一个相等的子节点则表示第一个公共子节点。

public

2.分别统计两个链表的长度while(cur1!null){cur1cur1.next;l1;}while(cur2!null){cur2cur2.next;l2;}//

重新获取头节点地址cur1pHead1;cur2pHead2;//

a0;while(asub){cur1cur1.next;a;}

}if(l1l2){int

a0;while(asub){cur2cur2.next;a;}

}//

5.同时遍历两个链表,当碰到第一个相等的子节点则表示第一个公共子节点while(cur2!cur2){cur2cur2.next;cur1cur1.next;}

return

我们可以先将链表中的所有数据添加到集合中再针对集合同时从首尾遍历比较数据是否相同。

public

(!Objects.equals(list.get(start),

list.get(last)))

我们也可以先将链表中的所有数据添加到栈中再次遍历链表同时进行出栈比较数据是否相同。

public

题解我们可以先创建一个新的链表用来保存结果再逐个比较每个节点的数值使用新的链表链接较小值节点并令较小值节点链表指针移动当有一方为null时停止比较令新链表链接上另一条链表。

public

重新创捷一个节点用于链接避免新链表头节点指针丢失ListNode

head

至多一条链表为null并且不为null的链表都为较大值直接连接上即可head.next

list1

目前我们只在此利用最暴力的解法要求合并N个我们是不是可以延伸上一题合并两条的解法即将合并k条转换为两条两条合并逐渐合并

public

重新创捷一个节点用于链接避免新链表头节点指针丢失ListNode

head

至多一条链表为null并且不为null的链表都为较大值直接连接上即可head.next

list1

必然位于中间。

当链表长度为奇数时快指针刚好移动到末尾节点慢指针移动到中间节点当链表长度为偶数时快指针刚好移动到null节点慢指针移动到中间的第二个节点节点由于fast

null

与上一题类似我们也可以使用快慢指针不同的是我们需要先将fast

向后遍历到第k1个节点

当快指针移动到null时慢指针刚好移动到倒数第k个节点while

(fast

仔细观察可以发现旋转链表其实就是将最后n个元素移动到了链表前面因此我们可以利用与上一题寻找倒数第k个节点类似的方法寻找到第k1个节点为什么不是第k个呢因为我们需要从第k1个开始链接操作一波寻找过后刚好快指针指向链表末节点而慢指针指向第k1个节点此时就可以非常方便的开始链接操作了。

public

我们可以用HashSet依次遍历记录每个节点同时判断是否以及出现过如果出现过就代表为环否则不是环借此轻松解决。

我们也可以用双指针的思想来解决类似于两个速度不一样的人在操场上跑步在跑了N圈之后速度快的人一定会超圈速度慢的人。

public

本题移除链表元素可能会碰到三种情况即要删除的元素在链表的头部中部尾部而删除头部与删除中部及尾部的处理方法不一致如果我们单独处理将非常的繁琐这时我们可以引入一个虚拟头节点指向头节点这样我们是不是就可以剔除掉要删除的元素出现的头部的情况接下来我们相当于只需要处理要删除的元素出现在链表的中部以及尾部而这两种操作非常类似我们仅需要找到要删除元素的前驱节点即可轻松完成。

public

由于虚拟头节点仅用于排除头节点情况并不存储数据因此我们需要返回其nextreturn

个结点

类似不过我们要删除第k个节点则必须找到第k个节点的前驱节点才行而移除元素可能会碰到三种情况即要删除的元素在链表的头部中部尾部而删除头部与删除中部及尾部的处理方法不一致如果我们单独处理将非常的繁琐这时我们同样可以引入一个虚拟头节点指向头节点这样我们是不是就可以剔除掉要删除的元素出现的头部的情况

public

由于给定的链表是排好序的因此可以推出重复的元素在链表中出现的位置是连续的因此我们只需要对链表进行一次遍历就可以删除重复的元素。

具体地我们从指针

cur

cur.next。

当遍历完整个链表之后我们返回链表的头节点即可。

public

如果和下一位相等则指向下下位因为我们并不能确保当前元素和下下是否相等//

(temp.val