面试中链表的经典题目

链表节点描述

记录面试中常见的链表经典题型

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null
    }
}

单指针题型

双指针题型

1. 环形链表

题目描述： 力扣 141.环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：用 O(1)内存解决

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

变形：返回环形链表的入口节点
力扣 142.环形链表II
双指针第一次相遇：
设链表共有 a + b 个节点，链表头部到链表入口有 a 个节点（不计链表入口节点）， 链表环有 b 个节点
(1). fast 走的步数是 slow 步数的 2 倍，即 f = 2s
(2). fast 比 slow 多走了 n 个环的长度，即 f = s + nb (重合时 fast 比 slow 多走环的长度整数倍)
以上两式相减得：f = 2nb ，s = nb ，即 fast 和 slow 指针分别走了 2n ，n 个环的周长
分析：如果让指针从链表一直向前走，所有走到链表入口节点是的步数有 k = a + nb
而第一次相遇时 slow 恰好走了 nb 步，距离环的入口还需要走 a 步
此时令 fast 重新指向 head 节点，当 fast 走到入口节点恰好也是 a 步， 即 fast 指针和 slow 指针将在入口节点相遇
返回 fast 或者 slow ， 即为入口节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        //快指针追上慢指针，只能说明存在环路，但并不一定是环路的入口
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 此时 slow 行走了 nb 步 
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

2. 链表中倒数第 k 个节点

题目描述： 剑指Offer 22. 链表中倒数第 k 个节点
输入一个链表，输出该链表中倒数第k个节点。
输入： 1->2->3->4->5, 和 k = 2
输出： 4->5
分析： 快慢指针，只需要将快指针比慢指针先走 k 步即可
当快指针走到指针尾部，慢指针刚好停留在倒数第 k 个节点处

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        while(k > 0) {
            fast = fast.next;
            k --;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

3. 相交链表的起始节点

题目描述： 力扣 160.相交链表
编写一个程序，找到两个单链表相交的起始节点。

在节点 c1 开始相交

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 !=  p2){
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
        }
        return p1;
    }
}