LeetCode链表常用技巧(二)

寻找一个链表倒数第k个节点

剑指 Offer 22. 链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

这种类型的题目常用技巧是快慢指针

复制代码

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;//快指针
    ListNode slow = head;//慢指针
    for(int i = 0; i < k; i++){//先将快指针移动k步，使得快慢指针之间相隔k个节点
        fast = fast.next;
    }
    //快慢指针同时移动，当快指针移动到null时，慢指针的位置就是倒数第k个节点
    while(fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

再比如LeetCode19这道题，删除链表倒数第N个节点

在单链表中我们想要删除一个节点，必须找到节点的前一个节点，通过下列语句：pre.next = pre.next.next;所有我们想要删除倒数N个节点，那么我们先找到倒数第N+1个节点，然后使用删除语句即可：

复制代码

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode resHead = new ListNode(-1,head);
        ListNode nodeK = lastK(resHead,n+1);
        nodeK.next = nodeK.next.next;
        return resHead.next;
    }
    //返回倒数第K个节点
    public ListNode lastK(ListNode head,int k){
        ListNode slow = head,fast = head;
        for(int i = 0; i < k; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

寻找链表的中点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。LeetCode876题。找中点，我们通过快慢指针来解决，快指针每次走二步，慢指针每次走一步，当快指针走到链表结尾，慢指针所在的位置就是中点。

复制代码

public ListNode middleNode(ListNode head) {
    //快慢指针找中点
    ListNode fast = head,slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

环形链表

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

这种问题也可以使用快慢指针解决，快指针每次走二步，慢指针走一步，如果链表中有环，那么快慢指针最后必然会相遇，而且存在这样的关系，假定慢指针走了K步，那么快指针肯定走了2K步。

复制代码

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

这个问题还可以升级，如果存在环，怎么找链表的中环的启动节点呢？

复制代码

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next == null){//当链表为空或者只有一个元素的时候。链表不可以有环
        return null;
    }
    ListNode fast = head;//快指针
    ListNode slow = head;//慢指针
    while(fast != null && fast.next != null){
        fast = fast.next.next;//移动两步
        slow = slow.next;//移动一步
        if(slow == fast){
            //说明有环
            slow = head;
            while(slow != fast){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    return null;
}

两条链表是否相交

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

这种问题同样也可以使用双指针解答，两个指针分别指向链表头部，依次访问。

复制代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null){
        return null;
    }
    ListNode l1 = headA;
    ListNode l2 = headB;
    while(l1 != l2){
        if(l1 == null){//当链表访问完成，把另一条链表加在后面，继续访问
            l1 = headB;
        }else{
            l1 = l1.next;
        }
        if(l2 == null){
            l2 = headA;
        }else{
            l2 = l2.next;
        }
    }
    return l1;//如果相交就是返回的相交的点，不相交就是返回null
}