关于力扣:链表的基础oj

单链表根底题

OR36 链表的回文结构

https://www.nowcoder.com/ta/2016test?tag=581

对于一个链表，请设计一个工夫复杂度为O(n),额定空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保障链表长度小于等于900。

思路：已知长度小于等于900，那么逆置半个链表也能够看做O(1)

1.先找到两头结点，有两个就返回第二个

2.逆置midnode链表

class PalindromeList {public:    struct ListNode* middleNode(struct ListNode* head)    {        int count = 0;        struct ListNode* t = head;        while(t!= NULL)        {            ++count;            t = t->next;        }                int count1 = count/2;        t = head;        while(count1--)        {            t = t->next;        }             return t;    }struct ListNode* reverseList(struct ListNode* head){    struct ListNode* t = head;    int a[910] = {0};    int count = 0;    while(t != NULL)    {        a[count++] = t->val;        t = t->next;    }    struct ListNode* h =  ( struct ListNode*)malloc(sizeof( struct ListNode));    struct ListNode* coph = h;    coph->next = NULL;    for(int i=count-1;i>=0;--i)    {        struct ListNode* newnode =  ( struct ListNode*)malloc(sizeof( struct ListNode));        newnode->next = NULL;        newnode->val = a[i];        h ->next = newnode;        h = newnode;    }    return coph->next;}    bool chkPalindrome(ListNode* A)     {        // write code here        struct ListNode* midnode = middleNode(A);        struct ListNode* rhead = reverseList(midnode);                struct ListNode* t1 = A;        struct ListNode* t2 = rhead;        while(t2 != NULL)        {            if(t1->val != t2->val)                return false;            t1 = t1->next;            t2 = t2->next;        }        return true;    }};

141. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

给你一个链表的头节点 head ，判断链表中是否有环。

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

思路：先思考有没有环，没环链表遍历肯定会完结

如果有环，链表两个速度不一样的指针会在环外面追击，若相差速度为1则肯定能够相遇

bool hasCycle(struct ListNode *head) {    struct ListNode * slow = head;    struct ListNode * fast = head;         while(fast!= NULL && fast->next != NULL)    {        slow = slow->next;        fast = fast->next->next;                if(slow == fast)            return true;    }    return false;}

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不容许批改 链表。

思路：假如在有环的链表中，slow与fast在meet处相遇，设链表头结点到环的第一个结点共L，环的第一个结点到meet共x，整个环共c个结点。

能够看出，slow必然在第一圈和fast相遇。因为它们的间隔肯定小于一圈，就算slow走了一圈，fast就走了两圈，他们之间又差一圈，它们的速度差是1，fast在每一步之之后它们的相差间隔都缩小了1。

在第一次相遇时：

slow走了 l+x

fast走了l+nc+x == 2(l+x)

解得l = (n-1)c + c - x，也就是说：meet到环第一个结点的步数等于Head到环第一个结点的步数

 struct ListNode * hasCycle(struct ListNode *head)  {     struct ListNode * slow = head;     struct ListNode * fast = head;     while(fast!= NULL && fast->next != NULL)     {         slow = slow->next;         fast = fast->next->next;         if(slow == fast)             return slow;     }     return NULL;}ListNode *detectCycle(ListNode *head) {    struct ListNode *meet = hasCycle(head);    if(meet == NULL)return NULL;    struct ListNode *t1 = head;    struct ListNode *t2 = meet;    while(t1 != t2)    {        t1 = t1->next;        t2 = t2->next;    }    return t1;}