链表面试题：链表的回文结构+链表分割+相交链表+环形链表（思路+图文+代码详解）_回文结构 java

---

链表常见面试题

---

一、 链表的回文结构

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
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

二、链表分割

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
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

三、相交链表

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
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

四、环形链表

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;
     
    }
}

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

五、环形链表 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;
    }
}
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

点击移步博客主页，欢迎光临~