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个节点
LeetCode链表常用技巧(二)

在单链表中我们想要删除一个节点,必须找到节点的前一个节点,通过下列语句: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。
LeetCode链表常用技巧(二)

这种问题也可以使用快慢指针解决,快指针每次走二步,慢指针走一步,如果链表中有环,那么快慢指针最后必然会相遇,而且存在这样的关系,假定慢指针走了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;
}

两条链表是否相交

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
LeetCode链表常用技巧(二)

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

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
}
上一篇:【NowCoder.链表.OR36】链表的回文结构,多个知识点,含如何找到链表中间节点,如何翻转链表


下一篇:面试题 02.02. 返回倒数第 k 个节点