1.两数相加
题目解析：两个非负整数相加，且这两个非负整数的数字都是按照逆序存储在链表中，模拟两数相加的过程，且相加的结果也是逆序存储在链表中，返回一个存储结果的链表
算法讲解：模拟两数相加即可
这道题由于已经逆序存储要进行计算的两个数字了，这其实是方便我们操作的，因为进行加法操作时，也是从最低位先开始进行计算的，此时只要去模拟两数相加的过程即可
因为两数相加会出现进位的情况，只需创建一个变量t去记录进位的情况，每次向链表中增加新节点时，添加t的个位数即可，在下一个数相加之前，将t的个位数删除
一个小细节：当相加到最后一位时，如果进位t>0，也是要将t考虑上去的
代码实现：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode newHead=new ListNode();
ListNode cur=newHead;
int t=0;
while(l1!=null&&l2!=null){
t=l1.val+l2.val+t;
cur.next=new ListNode(t%10);
l1=l1.next;
l2=l2.next;
cur=cur.next;
t=t/10;
}
if(l1==null){
while(l2!=null){
t=l2.val+t;
cur.next=new ListNode(t%10);
l2=l2.next;
cur=cur.next;
t=t/10;
}
}
if(l2==null){
while(l1!=null){
t=l1.val+t;
cur.next=new ListNode(t%10);
l1=l1.next;
cur=cur.next;
t=t/10;
}
}
if(t>0) cur.next=new ListNode(t);//考虑最后一位加，进位t的情况
return newHead.next;
}
}
//优化的写法
class Solution{
public ListNode addTwoNumbers(ListNode l1, ListNode l2){
ListNode newHead=new ListNode();
ListNode cur=newHead;
int t=0;
while(l1!=null || l2!=null || t>0){
if(l1!=null){
t+=l1.val;
l1=l1.next;
}
if(l2!=null){
t+=l2.val;
l2=l2.next;
}
cur.next=new ListNode(t%10);
cur=cur.next;
t/=10;
}
return newHead.next;
}
}2.两两交换链表的节点
题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
题目解析：交换链表中相邻节点
算法讲解：画图画图
第一个细节：创建一个新的头结点
创建一个新的头结点是为了方便统一操作，因为交换前两个相邻节点的操作和交换后面相邻节点的操作是有点不一样的，交换前两个头结点时，不涉及到前一个节点next的改变，而在交换从第2个节点后面的节点时，是会涉及到一个前next节点的改变的。
此时就可以直接创建一个新的头结点，让新的头结点执行原来的头结点
第二个细节：定义4个指针
如下图
先以交换1和2为例，交换之后的图如下，可知，交换的操作就是让
prev.next=next;
next.next=cur;
cur.next=nnext
第3个细节：循环结束的条件
当节点个数为偶数个时，循环结束的条件就是cur==null，如下图
当节点个数是奇数个时，循环结束的条件是next==null，如下图
代码实现：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode newHead=new ListNode();
ListNode prev=newHead;
if(head==null || head.next==null) return head;
ListNode cur=head;
ListNode next=cur.next;
ListNode nnext=next.next;
while(cur!=null&&next!=null){
prev.next=next;
next.next=cur;
cur.next=nnext;
prev=cur;
cur=nnext;
if(cur!=null) next=cur.next;
if(next!=null) nnext=next.next;
}
return newHead.next;
}
}3.重排链表
题目解析：将链表按照题目的要求进行重排列
算法讲解：
第一步：找中间节点
第二步：将后面一部分的链表进行逆序，使用头插法进行逆序
逆序有两种方案：
第一种方案：以slow.next为起点开始逆序
第一种方案在节点个数是奇数个时，是一种正确的方案，但是在偶数个的情况下，在这道题的排列规则下，也是正确的，假设链表中有4个节点，如下图，slow是中间节点，我们发现，即使进行重排列之后，3也是一直连在2的后面的，所以此时就可以放心大胆得将3直接放在2的后面
第二种方案：以slow为起点来开始逆序
第二种方案在节点个数为偶数个还是奇数个的情况下都是可以的
但是尽量要选择以slow.next为起点来逆序链表，因为后面是要将链表进行合并的，在进行链表的合并时，是要将链表分解成两个链表来合并的，为了方便讲链表拆成两个链表，要选择第一种方案（此时直接将slow.next==null就可以直接将链表拆分为2个链表），如果选择的是第二种方案，逆序之后，此时就不会有一个确定的节点将链表拆分成两个链表
第三步：合并两个链表
代码实现：
class Solution {
public void reorderList(ListNode head) {
//1.寻找中间节点-->快慢指针
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
//2.将后面部分链表进行逆序-->头插法
ListNode head2=new ListNode();
ListNode cur=slow.next;
while(cur!=null){
ListNode next=cur.next;
cur.next=head2.next;
head2.next=cur;
cur=next;
}
slow.next=null;//将链表拆分成两个链表
//3.合并链表-->双指针
ListNode cur1=head;
ListNode cur2=head2.next;
ListNode ret=new ListNode();
ListNode prev=ret;
//只需判断cur1，因为是以slow.next来拆分链表，也就是说前面部分的链表的长度一定是大于后面部分链表的长度
while(cur1!=null){
//先连接第一个链表
prev.next=cur1;
prev=cur1;
cur1=cur1.next;
if(cur2!=null){
prev.next=cur2;
prev=cur2;
cur2=cur2.next;
}
}
}
}4.合并K个升序链表---高频笔试面试题
题目链接：23. 合并 K 个升序链表 - 力扣（LeetCode）
题目解析：合并K个升序链表
算法讲解：
解法一：基于小根堆来解决
先获取到lists中每一个链表的头结点，将每个头结点都存到小根堆中（在小根堆中，堆顶就是最小值），然后取小根堆的堆顶元素，并将其连接到一个虚拟头结点中，然后再让对应链表的节点往后走，，节点往后走后，如果该节点值不是null，则将该节点在存到小根堆中，知道小根堆中没有元素
代码实现：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//1.创建小根堆
PriorityQueue<ListNode> heap=new PriorityQueue<>((v1,v2)->v1.val-v2.val);
//2.将头结点存到小根堆
for(ListNode head : lists){
if(head!=null) heap.offer(head);
}
//3.获取小根堆的堆顶元素
ListNode newHead=new ListNode();
ListNode perv=newHead;
while(!heap.isEmpty()){
ListNode tmp=heap.poll();
perv.next=tmp;
perv=tmp;
if(tmp.next!=null) heap.offer(tmp.next);
}
return newHead.next;
}
}解法二：分治---递归
题目是要求我们将K个升序链表进行合并，此时我们可以先将K个链表从中间划分为两部分，这两部分为[left,mid]和[mid+1,right]，分别先让这两部分的链表合并起来，那么如何分别将这两部分的链表合并起来呢?依旧是分别将这两部分的链表一份为二，然后依次类推下去
如下图
代码实现：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists,0,lists.length-1);
}
public ListNode merge(ListNode[] lists,int left,int right){
if(left>right) return null;//链表为空
if(left==right) return lists[left];//left或者right都可以
//将链表一分为二
int mid=(left+right)/2;
//[left,mid]和[mid+1,right]
ListNode l1=merge(lists,left,mid);
ListNode l2=merge(lists,mid+1,right);
//合并链表
return mergeTwoList(l1,l2);
}
public ListNode mergeTwoList(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
ListNode head=new ListNode();
ListNode prev=head;
ListNode cur1=l1;
ListNode cur2=l2;
while(cur1!=null&&cur2!=null){
if(cur1.val<=cur2.val){
prev.next=cur1;
prev=cur1;
cur1=cur1.next;
}else{
prev.next=cur2;
prev=cur2;
cur2=cur2.next;
}
}
if(cur1!=null) prev.next=cur1;
if(cur2!=null) prev.next=cur2;
return head.next;
}
}5.K个链表的翻转
题目链接：25. K 个一组翻转链表 - 力扣（LeetCode）
题目解析：如图所示
算法讲解：模拟
第一步：先求出需要逆序多少组，假设为n组
第二步：重复n次，长度为k的链表的逆序即可
一个细节：
因为我是采用头插的方式进行链表的逆序，此时假设我们已经完成了一次的长度为k的链表的逆序，此时如下图
此时如果进行下一次的逆序，此时就不是将节点直接插在head的后面了，而是要要将逆序的节点拼接在1节点的后面，则此时就需要用一个新的变量tmp来记录，在进行每一次长度为k的逆序时，先记录开始逆序的头结点，然后再每一次长度为k的逆序结束后，让prev=tmp
如下图
最后，还需要将不需要逆序的那部分链表拼接起来，即让prev.next=cur
代码实现：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int count=0;
ListNode cur=head;
ListNode newHead=new ListNode();
ListNode prev=newHead;
int _k=k;
while(cur!=null){
count++;
cur=cur.next;
}
cur=head;
count=count/k;
while(count>0){
ListNode tmp=cur;//记录逆序时的头结点
while(k>0){
ListNode next=cur.next;
cur.next=prev.next;
prev.next=cur;
cur=next;
k--;
}
k=_k;
prev=tmp;//变换prev
count--;
}
prev.next=cur;//拼接无需逆序的部分链表
return newHead.next;
}
}数据结构阶段的链表面试题
1.移除链表元素
题目链接：203. 移除链表元素 - 力扣（LeetCode）
题目解析：将链表中val==val的节点给删除掉
算法讲解：创建一个新的头结点
可以先创建一个新的头结点，接着去遍历链表，将节点值不等于val的节点尾插到新的头结点，最后返回newHead.next
小细节：如果链表中最后的一个的节点值等于val，此时就会出现新链表中尾插的最后一个节点还是会指向最后一个节点，如下图
代码实现：
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null) return null;
ListNode newHead=new ListNode();
ListNode prev=newHead;
ListNode cur=head;
while(cur!=null){
if(cur.val!=val){
prev.next=cur;
prev=cur;
}
cur=cur.next;
}
if(prev.next!=null&&prev.next.val==val) prev.next=null;
return newHead.next;
}
}2.反转一个单链表
题目描述：反转一个链表
算法讲解：头插法
创建一个新的头结点，然后遍历链表，将遍历的节点头插到新节点的后面
头插的思路：
头插的时候，先改变cur.next，在去改变newHead.next，但是此时cur.next就消失了，所以在每次逆序前要创建一个变量来记录cur.next
头插的思路如下图
代码实现：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead=new ListNode();
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=newHead.next;
newHead.next=cur;
cur=next;
}
return newHead.next;
}
}3.链表的中间节点
题目链接：876. 链表的中间结点 - 力扣（LeetCode）
题目解析：寻找链表的中间节点，如果有两个中间节点，返回第2个中间节点即可
算法讲解：快慢双指针
定义一个fast快指针和一个slow慢指针，fast一次走两步，slow一次走一步
当节点个数是奇数个时，循环结束的条件为fast.next==null，如下图
当节点个数为偶数个时，循环结束的条件为fast==null如下图
代码实现：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}4.删除链表的倒数第K个节点
题目链接：LCR 021. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
题目解析：删除链表的倒数第K个节点
算法讲解：
正难则反，题目让我们删除链表的倒数第K个节点，我们可以转换为删除链表的第N个节点，假设链表的节点个数为count，则N=count-k+1
此时第N个节点就是删除的节点，此时可以创建一个新节点newHead，将不用删除的节点进行尾插到newHead上面
一个小细节：如果1题目要求我们删除的是倒数第1个节点，假设倒数第1个节点是last，倒数第2个节点是cur，此时进行尾插时会执行prev.next=cur，但是此时cur.next还是指向last，所以每次在尾插的最后时，要将cur.next=null
代码实现：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode cur=head;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
cur=head;
//计算第几个节点是删除的节点--del
int del=count-n+1;
ListNode newHead=new ListNode();
ListNode prev=newHead;
int start=1;
while(cur!=null){
ListNode next=cur.next;
//尾插
if(start!=del){
prev.next=cur;
prev=cur;
cur.next=null;//细节
}
start++;
cur=next;
}
return newHead.next;
}
}5.链表分割
题目链接：链表分割_牛客题霸_牛客网
题目解析：将链表中val<x的节点排在其余的节点之前，且不能改变原来的数据顺序
算法讲解：分段+合并
可以向将链表分为两部分，其中一部分中的节点的val是小于x的，另一部分中的节点的val是大于等于x的
实现分段的思路：
先创建4个新的节点，bs和be，as和ae，bs和be这两个节点之间存的是都是val<k的节点，as和ae这两个节点之间存的都是val>=k的节点
也就是说，当遇到val>k的节点，就尾插到bs和be这段链表，当遇到val<=k的节点，就尾插到as和ae这段链表
此时分割玩链表后可能会出现两种情况
第一种情况：bs到be这一段依旧是空链表，此时直接返回as到ae这段链表即可
第二种情况：bs到be这一段不是空链表，此时要合并链表，让be.next=as.next
还有一个小细节：要将合并后的链表中的最后一个节点的next改为null
代码实现：
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs=new ListNode(0);
ListNode be=bs;
ListNode as=new ListNode(0);
ListNode ae=as;
ListNode cur=pHead;
while(cur!=null){
//尾插
if(cur.val<x){
be.next=cur;
be=cur;
cur=cur.next;
}else{
ae.next=cur;
ae=cur;
cur=cur.next;
}
}
if(bs.next==null) return as.next;
//走到这里代表bs到be间不是空链表
be.next=as.next;//合并链表
ae.next=null;//细节，将最后节点的next置为null
return bs.next;
}
}6.链表的回文结构
题目链接：链表的回文结构_牛客题霸_牛客网
题目解析：判断一个链表是否是回文结构
算法讲解：
第一步：找出链表的中间节点
第二步：将中间节点后面的链表进行翻转
第三部：此时链表就会变成下图中的样子，如下图
此时让head往后走，slow往前走，如果遇到head.val != slow.val的情况，那么链表就不是回文结构，此时直接返回false即可
还有一个小细节，head和slow走的过程中，要去判断链表节点个数是偶数个的情况，如下图，如果遇到head.next=slow的情况，说明链表就是回文结构，此时直接返回false
代码实现：
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode head=A;
//1.寻找中间节点
ListNode fast=A;
ListNode slow=A;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
//2.翻转slow后面的链表
ListNode cur=slow.next;
while(cur!=null){
ListNode next=cur.next;
cur.next=slow;
slow=cur;
cur=next;
}
//3.判断回文结构
while(head!=slow){
if(head.val!=slow.val) return false;
if(head.next==slow) return true;//考虑偶数个情况
slow=slow.next;
head=head.next;
}
//代码走到这里，说明head==slow,代表是回文结构
return true;
}
}7.相交链表
题目解析：找出并返回两个单链表相交的起始节点，如果不存在，则返回null
算法讲解：分别计算两条链表的长度，求出两条链表的长度差，假设长度差为sub，则让长的链表先走sub步，然后两条链表在一起走，直到相遇，此时相遇的节点就是相交的起始节点
代码实现：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int len1=0;
int len2=0;
ListNode cur1=headA;
ListNode cur2=headB;
while(cur1!=null){
len1++;
cur1=cur1.next;
}
while(cur2!=null){
len2++;
cur2=cur2.next;
}
//计算长度差,l指向长链表，s指向短链表
ListNode l=headA;
ListNode s=headB;
int sub=len1-len2;
if(len2>len1){
sub=len2-len1;
l=headB;
s=headA;
}
//长链表先走sub步
while(sub>0){
l=l.next;
sub--;
}
while(l!=s){
l=l.next;
s=s.next;
}
return l;
}
}8.环形链表
题目解析：判断链表中是否存在环
算法讲解：快慢指针
定义一个快指针和一个慢指针，让快指针一次走两步，让慢指针一次走一步，如果链表中不存在环，那么fast最后又两种情况，在节点个数为偶数个的情况下，最终fast==null，在节点个数为奇数个的情况下，最终fast.next==null，如果出现这两种情况，说明链表中不存在环，此时直接返回false
如果链表中有环，快指针肯定是先进环，慢指针肯定是后进环，因为快指针的速度比慢指针的速度快，所以fast一定会与slow相遇，如果相遇，则说明链表中有环（前提条件是快指针必须一次走两步，慢指针一次走一步），此时直接返回true
代码实现：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast) return true;//相遇，有环
}
//走到这里，代表没环
return false;
}
}9.环形链表 II
题目链接：142. 环形链表 II - 力扣（LeetCode）
题目解析：找出并返回链表中开始入环的第一个节点
算法讲解：
如下图
所以，先找出相遇的位置，因为L=R-X，所以一个节点cur从头结点开始往后走，一个节点从相遇的节点往前走，直到两个节点相遇，相遇的位置就是入环的第一个节点
代码实现：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
ListNode cur=head;
//找出相遇的位置
while(true){
if(fast==null || fast.next==null) return null; //没环的情况
slow=slow.next;
fast=fast.next.next;
if(slow==fast) break;
}
while(cur!=slow){
cur=cur.next;
slow=slow.next;
}
return cur;
}
}