(2)leetcode 234.回文链表 141.环形链表

234.回文链表

题目链接

234.回文链表

解题思路与代码

获取链表的中间段。

我们将mid这个节点记录下来，然后将这段链表反转，以下是反转的逻辑，最后我们将pre返回就是结果，就是通过中间变量tem记录位置从而实现链表的反转

最后结果比较的的时候，就变成了如图形式

此时就很简单了，我们两边遍历head和head2进行比较，一旦不相同就返回false，比较结束没有返回false说明是回文链表，返回true.

（c++代码）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

ListNode* reverseList(ListNode* cur) {
    ListNode* pre = NULL;
    while(cur != NULL) {
        ListNode* tem = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tem;
    }
    return pre;
}

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != NULL && fast->next != NULL) {
        slow = slow ->next;
        fast = fast->next->next;
    }
    return slow;
}

    bool isPalindrome(ListNode* head) {
        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid);

        while(head != mid) {
            if(head->val != head2 ->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

141.环形链表

题目链接

141.环形链表

解题思路与代码

举例，像这个，我们从head开始遍历，每次遍历的时候，遍历过一遍就存入set, 如果有环的话，遍历到重复的结点时，就返回true。

像这个，遍历到最后就是到了NULL，跳出循环，然后返回false.

(c++代码)

/**
 * 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) {
        unordered_set<ListNode*> st;
        while(head != NULL) {
            if(st.find(head) != st.end()) {
                return true;
            }
            st.insert(head);
            head = head ->next;
        }
        return false;
    }
};