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...