链表之十大经典面试题【Java&LeetCode】

1.删除链表中等于给定值 val 的所有节点。

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

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
删除前：

删除后：

思路

分情况：
1.当链表为空时，直接返回null。
2.当链表不为空时，定义一个前驱节点prev和cur，遍历链表，当cur.val == val时，如上图例子，要删除32，直接让prev.next=cur.next，就完成了删除操作，cur=cur.next继续遍历链表，当删除的节点为最后一个节点时，将prev.next ==null（置空）。
3.当删除完成之后需要确定头节点val是否是要删除的值，如果是返回head.next；如果不是就返回head。

代码展示

classSolution{publicListNoderemoveElements(ListNode head,int val){if(head ==null)returnnull;ListNode prev = head;ListNode cur = head.next;while(cur!=null){if(cur.val ==val){
                prev.next = cur.next;
                cur = cur.next;}else{
                prev = cur;
                cur = cur.next;}}if(head.val == val){
            head = head.next;}return head;}}

2.反转一个单链表。

题目链接: 反转一个单链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

反转前：

反转后：

思路

分情况：
1.当链表为空，直接返回null；
2.当链表只有一个头节点时，返回head；
3.当链表有两个以上节点时，原地移动链表， 定义一个cur节点，cur=head.next；定义一个curNext节点来暂存cur之后的节点，以防再反转链表时将后面的节点丢失，先将head置空，
cur.next=head;
head=cur;
cur=curNext; 依次循环直到 cur为空 即反转完成。

代码展示

classSolution{publicListNodereverseList(ListNode head){if(head ==null)returnnull;if(head.next ==null)return head;ListNode cur = head.next;
        head.next =null;while(cur !=null){ListNode curNext =cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;}return head;}}

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

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

引入 快慢指针

思路

使用快慢指针，慢指针每次走一步，快指针一次走两步，当快指针走到终点时，慢指针刚好走到链表的中间位置。
当链表节点为奇数时， 当fast.next == null时，不再循环；
当链表节点为偶数时，当 fast ==null时，不再循环；

代码展示

classSolution{publicListNodemiddleNode(ListNode head){if(head ==null){returnnull;}if(head.next==null){return head;}ListNode slow = head;ListNode fast = head;while(fast !=null&& fast.next !=null){
            slow=slow.next;//一次走一步
            fast=fast.next.next;//一次走两步}return slow;}}

4.链表中倒数第k个结点

题目链接:链表中倒数第k个结点

思路

使用快慢指针 ，让fast比slow快k-1步（k-1加上fast本身就是k步），当fast.next==null时，此时的fast比slow快了k步，就找到了倒数第k个数。
1.当头为空，或者k小于0，那么链表为空，返回null；
2.如果k过大，fast可能已经是null了，所以每次循环都要判断一下fast是否为空，防止出现空指针异常；
3.slow和fast一起走，当fast.next=null时，slow正好走到倒数第k个节点处。

代码展示

publicclassSolution{publicListNodeFindKthToTail(ListNode head,int k){//进行特判if(head ==null|| k <0)returnnull;ListNode slow = head;ListNode fast = head;while(k >0){
            k--;if(fast ==null)//如果k过大，fast可能已经是null了，所以每次循环都要判断一下fast是否为空，防止出现空指针异常returnnull;
            fast = fast.next;}while(fast !=null){
            fast = fast.next;
            slow = slow.next;}//此时slow和fast一起走，当fast.next=null时，slow正好走到倒数第k个节点处return slow;}}

5.合并两个有序链表

题目链接:合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路

定义一个虚拟节点，然后一次将两个链表的节点通过由大到小 升序 的顺序串起来

代码展示

classSolution{publicListNodemergeTwoLists(ListNode list1,ListNode list2){ListNode newNode =newListNode(-1);//虚拟节点ListNode tmp = newNode;//定义一个虚拟节点while(list1 !=null&& list2 !=null){if(list1.val < list2.val){
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;}else{
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;}//通过比较两个节点大小来确定下一个要串联的节点}if(list1 ==null){
                tmp.next = list2;}else{
                tmp.next = list1;}return newNode.next;}}

6.链表分割

题目链接:链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路

1.先令cur=head，把链表分成两段，第一段为小于目标值得，第二段为大于等于目标值的

2.让cur遍历链表并判断节点放入哪一段里，直到cur==null；

3.若cur.val<x，把cur尾插法到第一段里（分为是否第一次，如是第一次放进去就行了），若cur.val>=x，一样的方法

4.循环结束后把第二段尾插到第一段最后就行了，返回bs

5.最后要判断所有节点都在某一段的情况，若都在第二段，头结点就应是as

6.在判断若第二段有节点，则要把第二段ae.next设为null，防止链表成环

代码展示

publicclassPartition{publicListNodepartition(ListNode pHead,int x){// write code hereListNode cur = pHead;ListNode bs =null;ListNode be =null;ListNode as =null;ListNode ae =null;while(cur !=null){//当cur的值小于xif(cur.val < x){if(bs ==null){
                    bs = cur;
                    be = cur;}else{
                    be.next = cur;
                    be = be.next;}}else{//当cur的值大于xif(as ==null){
                    as = cur;
                    ae = cur;}else{
                    ae.next = cur;
                    ae = ae.next;}}
            cur = cur.next;}//当链表中没有小于x的值时if(bs ==null){return as;}
        be.next = as;//当链表中最后一个元素不是ae时，需要将ae的next置空if(as !=null){
            ae.next =null;}return bs;}}

7.链表的回文结构

题目链接:链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

思路

首先我们必须得了解什么叫回文链表

例如：1->2->3->2->1, 2->3->3->2,正向遍历和反向遍历链表的顺序一样，那么我们要如何进行判断？

1.先找出链表的中间位置

2.将中间位置以后的节点进行反转

3.一个从头遍历，一个从后往前遍历，判断两个数字是否相等（找出中间节点和反转链表可以参考 第三题【返回链表中间节点】）

代码展示

publicclassPalindromeList{publicbooleanchkPalindrome(ListNode head){ListNode fast = head;ListNode slow = head;while(fast !=null&& fast.next !=null){
            fast =fast.next.next;
            slow = slow.next;}//此时slow已经走到了中间位置ListNode cur = slow.next;while(cur !=null){ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;}//将slow之后的都反转while(head != slow){if(head.val != slow.val){returnfalse;}if(head.next == slow){returntrue;}
             head = head.next;
            slow = slow.next;}returntrue;}}

8.相交链表

题目链接:相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路

1.先分别求出两个链表的长度，让pl永远指向长链表
2.计算出两个链表的长度差len，让长链表先走len步，然后两个链表再一起走，直到两个链表的结点相同

代码展示

publicclassSolution{publicListNodegetIntersectionNode(ListNode headA,ListNode headB){if(headA ==null|| headB ==null){returnnull;}ListNode pl = headA;//pl指向长的链表ListNode ps = headB;//ps指向短的链表//1、分别求长度int lenA =0;int lenB =0;while(pl !=null){
            lenA++;
            pl = pl.next;}while(ps !=null){
            lenB++;
            ps = ps.next;}//需要重新修改指向
        pl = headA;
        ps = headB;//2、已经知道两个链表的长度了int len = lenA-lenB;if(len <0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;}//pl永远指向 最长的那个链表   ps永远指向最短的那个链表//3、就是让最长的链表走len步while(len !=0){
            pl = pl.next;
            len--;}//4、一人一步走 直到相遇while(pl != ps){
            pl = pl.next;
            ps = ps.next;}//5、是不是两个都是null-》没有相交if(pl ==null){returnnull;}return pl;}}

9.环形链表

题目链接:环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路

环形链表由链表中的某一个节点，一直找next指针，一定会再次到达这个节点，这样的链表就说是有环的，并且带环的链表每个节点的next 指针，都不为null。
引入快慢指针，如果有环，一定会相遇。

代码展示

publicclassSolution{publicbooleanhasCycle(ListNode head){if(head ==null|| head.next ==null){returnfalse;}ListNode fast =head;ListNode slow = head;while(fast !=null&& fast.next !=null){
            fast = fast.next.next;//快指针比慢指针多走一步
            slow = slow.next;if(fast == slow){returntrue;}}returnfalse;}}

10.环形链表 II

题目链接:环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路

1.先判断列表是否有环

2.当列表有环时

当slow和fast相遇时，让fast重新回到head位置，两个每次都走一步，slow和fast走过的路程一样，即L=x,此时相遇的位置就是环的入口点

代码展示

publicclassSolution{publicListNodedetectCycle(ListNode head){ListNode fast = head;ListNode slow = head;while(fast !=null&& fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;if(fast == slow){break;}}if(fast ==null|| fast.next ==null){returnnull;}
 
        fast = head;while(fast != slow){
            fast = fast.next;
            slow = slow.next;}return fast;}}