链表中倒数第k个节点
题目描述leetcode :删除链表的倒数第N个节点面试题23:链表中环的入口节点leetcode：环形链表leetcode:环形链表 II
题目描述
输入一个链表，输出倒数第k个节点
思路：定义两个指针，p-q = k-1，当p遍历结束，q就是第k个节点。 考虑情况：
第k个不存在，p-q < k如果k==0，则只需要一个p
类似题目
leetcode :删除链表的倒数第N个节点
删除链表的倒数第N个节点 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
考虑情况：
k0， 定义一个p-q1，直接删除最后一个删除的是头节点：对比q和头节点没有删除：记录步数
p - q
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head==nullptr) return head;
ListNode *p = head, *q = head;
int count=0;
while(count < n)
{
if(q->next != nullptr)
{
q = q->next;
count ++;
}
else
{
break;
}
}
if(count == n-1)
{
if(head->next == nullptr) return nullptr;
else return head->next;
}
while(q->next != nullptr)
{
p = p->next;
q = q->next;
}
if(n==1)
{
p->next = nullptr;
return head;
}
p->next = p->next->next;
return head;
}
};
执行用时 : 8 ms, 在Remove Nth Node From End of List的C++提交中击败了97.86% 的用户 内存消耗 : 8.5 MB, 在Remove Nth Node From End of List的C++提交中击败了87.64% 的用户
面试题23:链表中环的入口节点
一个链表中包含环，如何找到环的入口节点。
思路：如果环有n个节点，第一个指针先走n，然后第二个指针开始走。当两个指针相遇，就是入口节点。
how：如何得到环中节点的数量？ 一快一慢指针，两个指针相遇一定在环内，从这个节点出发，一边移动一边计数，直到再次到这个节点。
leetcode：环形链表
环形链表 给定一个链表，判断链表中是否有环。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr) return false;
ListNode *fast = head->next;
ListNode *slow = head;
while(fast != nullptr && slow!=nullptr)
{
if(fast == slow) return true;
slow = slow->next;
fast = fast->next;
if(fast != nullptr) fast = fast->next;
}
return false;
}
};
执行用时 : 12 ms, 在Linked List Cycle的C++提交中击败了99.08% 的用户 内存消耗 : 10 MB, 在Linked List Cycle的C++提交中击败了11.01% 的用户
leetcode:环形链表 II
环形链表 II 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* hasCycle(ListNode *head) {
if(head==nullptr) return nullptr;
ListNode *fast = head->next;
ListNode *slow = head;
while(fast != nullptr && slow!=nullptr)
{
if(fast == slow) return fast;
slow = slow->next;
fast = fast->next;
if(fast != nullptr) fast = fast->next;
}
return nullptr;
}
ListNode *detectCycle(ListNode *head) {
ListNode *start = hasCycle(head);
if(start == nullptr) return nullptr;
int count = 1;
ListNode *p = start->next;
while(p!= start)
{
p = p->next;
count ++;
}
ListNode *first = head, *second = head;
for(int i=0; i<count; i++)
{
first = first->next;
}
while(first != second)
{
first = first->next;
second = second->next;
}
return first;
}
};
执行用时 : 16 ms, 在Linked List Cycle II的C++提交中击败了96.71% 的用户 内存消耗 : 9.7 MB, 在Linked List Cycle II的C++提交中击败了57.80% 的用户
