力扣面试常见150题:栈+链表(java+c++)
栈
有效的括号(20)
���定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
提示：
- 1 next->next;
}
return true;
}
};
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
两数相加(2)
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 val : 0;//同上
int c = tmp1 + tmp2 + jin;//进位加上这两个数之和
if(!res){//结果链表为空
res = cur = new ListNode(c % 10);//结果为和的个位数
}
else{//结果链表不为空
cur->next = new ListNode(c % 10);//当前结点为和的个位数
cur = cur->next;
}
jin = c / 10;//进位数
if(l1){//l1不为空
l1 = l1->next;
}
if(l2){
l2 = l2->next;
}
}
if(jin > 0){//最后的进位大于0，则加到最后
cur->next = new ListNode(jin);
}
return res;
}
};
//java版，击败100% /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res = null, cur = null; int jin = 0; while(l1 != null || l2 != null){ int tmp1 = l1 != null ? l1.val : 0; int tmp2 = l2 != null ? l2.val : 0; int c = tmp1 + tmp2 + jin; if(res == null){ res = cur = new ListNode(c % 10); } else{ cur.next = new ListNode(c % 10); cur = cur.next; } jin = c / 10; if(l1 != null){ l1 = l1.next; } if(l2 != null){ l2 = l2.next; } } if(jin > 0){ cur.next = new ListNode(jin); } return res; } }合并两个有序链表(21)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 next = list1;
list1 = list1->next;
}
else{
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return res->next;
}
};
//java版打败100% /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode res = new ListNode(-1), cur = res;//初始化，定义结果链表和当前链表 while(list1 != null && list2 != null){ if(list1.val Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
- 0 next];
map[cur] -> random = map[cur -> random];
cur = cur ->next;
}
return map[head];
}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map node_map;
Node* p = head;
while (p) {
if (!node_map.count(p)) {//哈希表里面没有当前结点p
Node* t = new Node(p->val);
node_map[p] = t;//哈希表插入值为val的结点
}
Node* n = node_map[p];//插入val值后的结点
if (p->next) {//插入next
if (!node_map.count(p->next)) {
Node* t = new Node(p->next->val);
node_map[p->next] = t;
}
n->next = node_map[p->next];
}
if (p->random) {//插入random
if (!node_map.count(p->random)) {
Node* t = new Node(p->random->val);
node_map[p->random] = t;
}
n->random = node_map[p->random];
}
p = p->next;
}
return node_map[head];
}
};
//高效写法
class Solution {
public:
unordered_map origin2new;
Node* copyRandomList(Node* head) {
if(!head){
return NULL;
}
if(origin2new.find(head) == origin2new.end()){
Node *newHead = new Node(head -> val);
origin2new[head] = newHead;
newHead -> next = copyRandomList(head -> next);
newHead -> random = copyRandomList(head -> random);
}
return origin2new[head];
}
};
//java /* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null){ return null; } Node cur = head; Map m = new HashMap(); while(cur != null){ m.put(cur, new Node(cur.val)); cur = cur.next; } cur = head;//复制val后重来插入next和random while(cur != null){ m.get(cur).next = m.get(cur.next); m.get(cur).random = m.get(cur.random); cur = cur.next; } return m.get(head); } }反转链表(206)
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; //前指针节点 ListNode curr = head; //当前指针节点 //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移 while (curr != null) { ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移 curr.next = prev; //将当前节点指向它前面的节点 prev = curr; //前指针后移 curr = nextTemp; //当前指针后移 } return prev; } }反转链表II(92)
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left next;//cur2下一个结点指向 pre->next = cur2;//pre下一个结点指向cur2 } return res->next; } }; class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 设置 dummyNode 是这一类问题的一般做法 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; for (int i = 0; i
法二:运用反转链表的方法 class Solution { private: void reverseLinkedList(ListNode *head) { // 也可以使用递归反转一个链表 ListNode *pre = nullptr; ListNode *cur = head; while (cur != nullptr) { ListNode *tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } } public: ListNode *reverseBetween(ListNode *head, int left, int right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 ListNode *dummyNode = new ListNode(-1); dummyNode->next = head; ListNode *pre = dummyNode; // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (int i = 0; i next; } // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 ListNode *rightNode = pre; for (int i = 0; i next; } // 第 3 步：切断出一个子链表（截取链表） ListNode *leftNode = pre->next; ListNode *curr = rightNode->next; // 注意：切断链接 pre->next = nullptr; rightNode->next = nullptr; // 第 4 步：同第 206 题，反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步：接回到原来的链表中 pre->next = rightNode; leftNode->next = curr; return dummyNode->next; } }; class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (int i = 0; i删除链表的倒数第N个结点(19)
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
提示：
- 链表中结点的数目为 sz
- 1 next;
delete res;
return res2;
}
};
//c++击败100%的写法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy -> next = head;
ListNode* p = dummy;
ListNode* q = dummy;
while(n--){
q = q -> next;
}
while(q -> next){
p = p -> next;
q = q -> next;
}
p -> next = p -> next -> next;
ListNode* ans = dummy -> next;
delete dummy;
return ans;
}
};
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { int cnt = 0; ListNode len = head; while(len != null){ cnt++; len = len.next; } int m = cnt - n; ListNode res = new ListNode(0, head); ListNode cur = res; for(int i = 1; i删除排序链表中的重复元素II(82)
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]
提示：
- 链表中节点数目在范围 [0, 300] 内
- -100 next->next != NULL){//cur下一个和下下一个都不空
if(cur->next->val == cur->next->next->val){//先两个对比
int x = cur->next->val;//相同值
while(cur->next != NULL && cur->next->val == x){//往后比较
cur->next = cur->next->next;//跳过
}
}
else{
cur = cur->next;
}
}
return res->next;
}
};
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null) { return head; } ListNode dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int x = cur.next.val; while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; } } else { cur = cur.next; } } return dummy.next; } }旋转链表(61)
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4 输出：[2,0,1]
提示：
- 链表中节点的数目在范围 [0, 500] 内
- -100 next = head;//成环
while(m--){
cur = cur->next;//根据移动次数往后遍历
}
ListNode* res = cur->next;//结果链表的头结点
cur->next = NULL;//尾结点next为空
return res;
}
};
class Solution { public ListNode rotateRight(ListNode head, int k) { if (k == 0 || head == null || head.next == null) { return head; } int n = 1; ListNode iter = head; while (iter.next != null) { iter = iter.next; n++; } int add = n - k % n; if (add == n) { return head; } iter.next = head; while (add-- > 0) { iter = iter.next; } ListNode ret = iter.next; iter.next = null; return ret; } }分隔链表(86)
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100
- 0 next];
map[cur] -> random = map[cur -> random];
cur = cur ->next;
}
return map[head];
}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map node_map;
Node* p = head;
while (p) {
if (!node_map.count(p)) {//哈希表里面没有当前结点p
Node* t = new Node(p->val);
node_map[p] = t;//哈希表插入值为val的结点
}
Node* n = node_map[p];//插入val值后的结点
if (p->next) {//插入next
if (!node_map.count(p->next)) {
Node* t = new Node(p->next->val);
node_map[p->next] = t;
}
n->next = node_map[p->next];
}
if (p->random) {//插入random
if (!node_map.count(p->random)) {
Node* t = new Node(p->random->val);
node_map[p->random] = t;
}
n->random = node_map[p->random];
}
p = p->next;
}
return node_map[head];
}
};
//高效写法
class Solution {
public:
unordered_map origin2new;
Node* copyRandomList(Node* head) {
if(!head){
return NULL;
}
if(origin2new.find(head) == origin2new.end()){
Node *newHead = new Node(head -> val);
origin2new[head] = newHead;
newHead -> next = copyRandomList(head -> next);
newHead -> random = copyRandomList(head -> random);
}
return origin2new[head];
}
};
The End