链表的特殊状态：相交链表、回文链表、环形链表

# 链表的特殊状态：相交链表、回文链表、环形链表

# 一、相交链表

# 剑指 Offer 52. 两个链表的第一个公共节点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currentA = headA, currentB = headB;
        while (currentA != currentB) {//'null'和'相等'都为终止条件
            currentA = currentA == null ? headB : currentA.next;
            currentB = currentB == null ? headA : currentB.next;
        }
        return currentA;
    }
}

1
2
3
4
5
6
7
8
9
10

# 二、回文链表

# 剑指 Offer II 027. 回文链表 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        //Step1: 快慢指针找到中间节点
        ListNode slow = head,fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //Step2: 链表反转后半部分（也可以反转前半部分比较）
        ListNode cur = slow,pre = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        //Step3: 判断是否为回文链表
        ListNode left = head;
        while(pre != null){
            if(left.val != pre.val) return false;
            left = left.next;
            pre = pre.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

☀️☀️☀️☀️☀️☀️题解二：题解一中Step1和Step2可以合并

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        //快慢指针找到中间节点并反转左半部分链表
        ListNode slow = head, fast = head;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            //反转左部分
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;//此处pre为反转的前半部分
            slow = tmp;
        }
        if(fast != null){//链表单数的时候，slow位于中间节点，后移一位，用后半部分和前半部分比较是否回文
            slow = slow.next;
        }
        //判断是否回文链表
        while (pre != null) {
            if(pre.val != slow.val) return false;
            slow = slow.next;
            pre = pre.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

# 三、环形链表

# 141. 环形链表 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        //快慢指针,快指针走两步，慢指针走一步
        ListNode slow = head,fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 剑指 Offer II 022. 链表中环的入口节点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //Step1: 快慢判断链表是否有环，并返回交点
        ListNode slow = head, fast = head;
        while(true){
            if(fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) break;
        }
        //Step2: 慢指针继续行走，另一指针从头开始走，二者交点为环的入口。
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#链表

← 链表的高级操作：链表的反转、合并、拆分数组篇：双指针技巧→