文章目录
链表常见面试题
一、 链表的回文结构
1.题目
2.思路
1.先通过快慢指针，找到中间结点
2.对中间结点后面的链表进行反转
3.指针从两端开始移动，如果符合回文结构，在奇数情况下相与，在偶数情况下相邻
3.图解
4.解题步骤
- 1.判断头结点是否为空，判断是否只有一个结点
- 2.设立快慢指针，找到中间的结点
- 3.设cur结点为中间结点的下一个结点,进行后面链表的反转
- 4.当cur为空时，说明slow到了末尾
- 5.让头结点和slow向中间移动
- 6.如果两端的值不等时，直接返回false
- 7.在奇数个结点的情况下，head和slow相遇
- 8.在偶数结点的情况下，head的下一个结点就是slow
5.代码
public boolean chkPalindrome() {
if (head == null) {
return false;
}
if (head.next == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
//寻找中间结点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//翻转
ListNode cur = slow.next;//cur代表当前需要翻转的结点
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//一个从前往后，一个从后往前，进行比较， 直到slow和head相遇
while (slow != head) {
if (head.val != slow.val) {
return false;
}
if (head.next == slow) {//走到这里两个val值一样，偶数情况
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
二、链表分割
1.题目
2.思路
1.比较x重新排序，且不能改变原来是顺序
2.新创建两个链表，链表A存储比x小的，链表B存比x大的
3.比较完后，将两个链表进行拼接
4.将末尾的next置为空
3.图解
4.解题步骤
- 1.设置A、B两个链表的头结点as、bs和尾结点ae 、be
- 2.cur的代替头结点移动
- 3.判断cur的值是否小于x,如果小于，存放进A链表中，大于存放进B链表中
- 4.因为A、B两个链表可能不会同时存在元素
- 5.如果A链表为空，返回B链表的内容，如果B链表为空，证明没进入循环，如果B链表不为空，返回B链表里的内容
- 6.A链表不为空，拼接两个链表
- 7.将末尾置为空 （为了避免置空时，空指针异常，要判断B链表是否为空）
- 8.返回拼接后的链表；
5.代码
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode Head, int x) {
ListNode cur = Head;
ListNode as = null;
ListNode ae = null;
ListNode bs = null;
ListNode be = null;
while(cur!=null){
if(cur.val<x){
if(as==null){
as = cur;
ae = cur;
} else{
ae.next = cur;
ae = cur;
}
}else{
if(bs==null){
bs = cur;
be = cur;
}else{
be.next = cur;
be = cur;
}
}
cur = cur.next;
}
//A/B两个链表可能不会同时存在元素
if(as==null){//A链表如果为空，返回B链表
return bs;//此时B链表要么为空要么不为空，不为空证明进入到了循环，返回B链表的内容，为空证明没进到循环里面
}
//A链表不为空，拼接两个链表
ae.next = bs;
if(bs != null){//判断；链表B不等于空，避免置空时空指针异常
be.next=null;//将末尾置为空
}
return as;
}
}
三、相交链表
1.题目
2.思路
1.先分别求出两个链表的长度，根据长度的差值，pl指向长链表 ps指向短链表
2.pl先移动,直到两个链表长度相等
3,pl和ps同时移动，直到相遇
3.图解
4.解题步骤
- 1.先判断两个头结点是否为空
- 2.用pl、ps分别指向两个链表的头结点
- 3.通过遍历分别求出两个链表的长度，（遍历完后要对pl、ps重新指向，不然会发生空指针异常）
- 4.根据长度的差值，pl、ps重新指向对应链表头结点
- 5.让pl先走len步，直到两个链表长度相等
- 6.pl和ps同时移动，直到相遇
- 7.返回此时的pl（即使pl,ps都为空，同样相等，返回值也是返回空，并不影响结果）
5.代码
public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
if (headA==null || headB==null){
return null;
}
//分别求两个链表的长度
int lenA = 0;
int lenB = 0;
MySingleList.ListNode pl = headA;
MySingleList.ListNode ps = headB;
while (pl != null) {
lenA++;
pl = pl.next;
}
while (ps != null) {
lenB++;
ps = ps.next;
}
int len = lenA - lenB;
//求完长度后，ps和pl为空了，要设置回去
pl = headA;
ps = headB;
//根据len的值修改指向
if (len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}//len为差值且一定是整数，pl指向长的链表
while (len != 0) {
pl = pl.next;
len--;
}
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
/* if (pl == null) {
return null;
}*/
return pl;
}
四、环形链表
1.题目
2.思路
1.利用快慢指针
2.fast每次走两步，slow每次走一步（
3.走别的倍数可能永远相遇不了，fast走两步相当于追击问题追一步，最坏情况为相差一圈的长度
4.直到相遇则证明链表中有环；（要排除都为空的情况）
3.图解
4.解题步骤
- 1.在头结点设置快慢指针
- 2.当fast不为空，并且fast的下一个结点不为空时，遍历链表
- 3.让fast每次走两步，slow走一步
- 4.当fast和slow相遇时，返回true
- 5.当走完循环，证明没有符合的条件，返回false;
5.代码
/**
* 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) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
五、环形链表 II
1.题目
2.思路
1.返回环开始的结点，没有环返回null
2.先找到相遇结点，根据下图推导出，x=y
3.让其中一个指针返回头结点，同时移动直到再次相遇
3.图解
4.解题步骤
- 1.在头结点设置快慢指针
- 2.遍历链表找到相遇的结点，结束循环
- 3.判断处理fast等于空和fast.next等于空的情况
- 4.把其中一个结点返回到头结点，两个指针同时移动相等速度
- 5.再次相遇的点就是环开始的结点
5.代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {//获取相遇结点
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
break;
}
}
if (fast ==null||fast.next==null){
return null;
}
slow = head;
while (fast!=slow){ //同时移动,相遇位置就是环的开始结点
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
本文含有隐藏内容，请 开通VIP 后查看