乐趣区

关于c++:Leetcode三道双指针链表题

jiezi

1. 返回倒数第 K 个结点

题目形容

题目链接：https://leetcode-cn.com/probl…

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例：
输出： 1->2->3->4->5 和 k = 2
输入： 4

快慢指针法

链表经典题，快慢指针，只需一次遍历。工夫复杂度 O(n)，空间复杂度 O(1)

int kthToLast(ListNode* head, int k) {
        ListNode* fast = head, *low = head;
        while(k--) {fast = fast -> next;}
        while(fast) {
            fast = fast -> next;
            low = low -> next;
        }
        return low -> val;
    }

2. 相交链表

题目形容

题目链接：https://leetcode-cn.com/probl…

编写一个程序，找到两个单链表相交的起始节点。

示例：

输出：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输入：Reference of the node with value = 8
输出解释：相交节点的值为 8（留神，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

注：skipA 和 skipB 仅做了解用，并不作为接口的参数

快慢指针

思路：由题目输出所给的提醒能够看出，如果两个链表有雷同的结点，那么在公共结点之前，两个链表别离有本人的子链表，而这两条子链表的长度差正好是两条链表的长度差（因为从公共结点开始两个链表都是雷同的）。晓得了这一点，就有了一个思路——假如两个链表长度差为 diff，那么让指向较长链表的指针先走 diff 步，而后两个指针同时走，再打消了长度差后，两个指针必然同时走到公共结点（如果有的话）。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return NULL;
        int len1 = 0, len2 = 0;
        ListNode *node1 = headA, *node2 = headB;
        while(node1) {
            node1 = node1 -> next;
            ++len1;
        }
        while(node2) {
            node2 = node2 -> next;
            ++len2;
        }
        int diff = len1 - len2;
        node1 = headA; node2 = headB;
        if(diff > 0) {while(diff--) {node1 = node1 -> next;}
        }
        else {while(diff++ < 0) {node2 = node2 -> next;}
        }

        while(node1 != node2) {
            node1 = node1 -> next;
            node2 = node2 -> next;
        }
        return node1;
    }

工夫复杂度：显然，两个链表都只遍历了两次，工夫复杂度为 O(m+n)
空间复杂度：O(1)

巧解法

思路：巧解法思路的精华在于，若两个链表长度为 a,b，那么 a +b=b+a。这就意味着，让两个链表的开端都指向对方的结尾，造成的两条新链表的长度是统一的。并且，如果两个链表有公共结点，那么造成的两条长链表的结尾必然有公共局部（因为两个原始链表原本就有公共局部，只是原来两个链表的长度可能不同，不好比拟，但两条长链表）。画出两个长链表高深莫测。基于这个思路，能够失去如下简洁代码：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return NULL;
        ListNode *node1 = headA, *node2 = headB;
        while(node1 != node2) {
            node1 = node1 ? node1 -> next : headB;
            node2 = node2 ? node2 -> next : headA; 
        }
        return node1;
    }

找到链表环入口

题目形容

题目链接：https://leetcode-cn.com/probl…

给定一个链表，如果它是有环链表，实现一个算法返回环路的结尾节点。

如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。

输出：head = [3,2,0,-4], pos = 1
输入：tail connects to node index 1
解释：链表中有一个环，其尾部连贯到第二个节点。

剑指 offer 经典题，快慢指针。

快慢指针法 

ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr)
        {
            slow = slow->next;
            // 无环的状况
            if (fast->next == nullptr)
            {return nullptr;}
            fast = fast->next->next;
            // 找到相交点
            if (fast == slow)
            {
                // 作为新的终点持续走
                ListNode* curr = head;
                while (curr != fast)
                {
                    fast = fast->next;
                    curr = curr->next;
                }
                return curr;
            }
        }

        return nullptr;
    }

工夫复杂度 O(n)，空间复杂度 O(1)。

附快慢指针为什么能胜利的数学证实：https://leetcode-cn.com/probl…

退出移动版