【数据结构】链表之十大经典面试题【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。

代码展示

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return  null;
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.反转一个单链表。

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

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

反转前：

反转后：

思路

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

代码展示

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

引入 快慢指针

思路

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

代码展示

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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个节点处。

代码展示

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {   //进行特判
        if(head == null || k < 0)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        while (k > 0){
            k--;
            if(fast == null)   //如果k过大，fast可能已经是null了，所以每次循环都要判断一下fast是否为空，防止出现空指针异常
                return null;
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }//此时slow和fast一起走，当fast.next=null时，slow正好走到倒数第k个节点处
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.合并两个有序链表

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

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

思路

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

代码展示

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newNode = new ListNode(-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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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，防止链表成环

代码展示

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur = pHead;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
         
        while(cur != null){
            //当cur的值小于x
            if(cur.val < x){
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{//当cur的值大于x
                if(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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

7.链表的回文结构

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

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

测试样例：

思路

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

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

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

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

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

代码展示

public class PalindromeList {
      public boolean chkPalindrome(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){
                return false;
            }
            if(head.next == slow){
                return true;
            }
             head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

8.相交链表

题目链接:相交链表

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

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

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

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

思路

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

代码展示

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         if(headA == null || headB == null) {
            return null;
        }
        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) {
            return null;
        }
        return pl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

9.环形链表

题目链接:环形链表

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

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

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

思路

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

代码展示

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        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;       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

10.环形链表 II

题目链接:环形链表 II

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

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

不允许修改 链表。

思路

1.先判断列表是否有环

2.当列表有环时

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

代码展示

public class Solution {
    public ListNode detectCycle(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) {
            return null;
        }
 
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23