(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;}
};