力扣Hot100每日一题[1,3]

160. 相交链表

题目列表: LeetCode 热题 HOT 100

解法一

使用哈希集合（C++中是unordered_set，Java中是HashSet）存储链表 $headA$ 节点，判断 $headB$ 中的节点是否在哈希集合中。

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 是分别是链表 $headA$ 和 $headB$ 的长度。需要遍历两个链表各一次。
• 空间复杂度：$O(m)$，其中 $m$ 是链表 $headA$ 的长度。需要使用哈希集合存储链表 $headA$ 中的全部节点。

C++代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *>set;ListNode *t = headA;while(t != nullptr){set.insert(t);t = t->next;}t = headB;while(t != nullptr){if(set.count(t)){return t;}t = t->next;}return nullptr;}
};

Java代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<ListNode>();ListNode temp = headA;while(temp != null){set.add(temp);temp = temp.next;}temp = headB;while(temp != null){if(set.contains(temp)){return temp;}temp = temp.next;}return null;}
}

解法二

相交链表（双指针，清晰图解）添加链接描述

C++代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *a = headA, *b = headB;while(a != b){a = (a != nullptr) ? a->next : headB;b = (b != nullptr) ? b->next : headA;}return a;}
};

Java代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a = headA, b = headB;while(a != b){a = (a == null) ? headB : a.next;b = (b == null) ? headA : b.next;}return a;}
}

236. 二叉树的最近公共祖先

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == p || root == q || root == nullptr) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if(left != nullptr && right != nullptr) return root;else if(left != nullptr) return left;else if(right != nullptr) return right;return nullptr; }
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//if(root == p || root == q || root == null) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p ,q);if(left == null) return right;if(right == null) return left;return root;}
}

234. 回文链表

206. 反转链表

迭代或递归实现
C++版本

//迭代
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *pre = nullptr, *now = head;while(now != nullptr){ListNode *next = now->next;now->next = pre;pre = now;now = next;}return pre;}
};
// 递归
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode *newhead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newhead;}
};

Java版本

// 迭代
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;while(head != null){ListNode temp = head.next;head.next = pre;pre = head;head = temp;}return pre;}
}
// 递归
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

回归本题
C++版本

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *pre = nullptr, *now = head;while(now != nullptr){ListNode *next = now->next;now->next = pre;pre = now;now = next;}return pre;}bool isPalindrome(ListNode* head) {ListNode *slow = head, *quick = head;while(quick->next != nullptr){slow = slow->next;quick = quick->next;if(quick->next != nullptr) quick = quick->next;}ListNode *rear = reverseList(slow);ListNode *a = head, *b = rear;while(a != slow){if(a->val != b->val) return false;a = a->next;b = b->next;}return true;}
};

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;while(head != null){ListNode temp = head.next;head.next = pre;pre = head;head = temp;}return pre;}public boolean isPalindrome(ListNode head) {ListNode slow = head, quick = head;while(quick.next != null){slow = slow.next;quick = quick.next;if(quick.next != null) quick = quick.next;}ListNode rear = reverseList(slow), a = head, b = rear;while(a != slow){if(a.val != b.val) return false;a = a.next;b = b.next;}return true;}
}