关于力扣:链表的基础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;
}