首页 > 代码库 > leetcode笔记
leetcode笔记
leetcode 笔记
Linked List
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
1 #include <string> 2 #include <cstdio> 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 8 struct ListNode { 9 int val; 10 ListNode *next; 11 ListNode(int x) : val(x), next(NULL) {} 12 }; 13 14 // 错误原因：res = res -> next;漏掉 15 class Solution { 16 public: 17 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 18 ListNode* res = new ListNode(0); 19 ListNode* new_head = res; 20 int sum = 0; 21 while (l1 || l2) { 22 if (l1) { 23 sum += l1 -> val; 24 l1 = l1 -> next; 25 } 26 if (l2) { 27 sum += l2 -> val; 28 l2 = l2 -> next; 29 } 30 res = res -> next = new ListNode(sum%10); // @1 31 sum /= 10; 32 } 33 if (sum) res -> next = new ListNode(sum); 34 return new_head -> next; 35 } 36 } 37 38 // 思路：避免类似444+556的情况，while中不要用&&
19. Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
1 #include <string> 2 #include <cstdio> 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 8 // Definition for singly-linked list. 9 struct ListNode { 10 int val; 11 ListNode *next; 12 ListNode(int x) : val(x), next(NULL) {} 13 }; 14 15 class Solution { 16 public: 17 ListNode* removeNthFromEnd(ListNode* head, int n) { 18 ListNode** t1 = &head, *t2 = head; 19 for(int i = 1; i < n; ++i) 20 { 21 t2 = t2->next; 22 } 23 while(t2->next != NULL) 24 { 25 t1 = &((*t1)->next); 26 t2 = t2->next; 27 } 28 *t1 = (*t1)->next; 29 return head; 30 } 31 }; 32 // 思路：待删节点定义为二级指针，将地址改变（tasty code o.o） 33 34 class Solution { 35 public: 36 ListNode* removeNthFromEnd(ListNode* head, int n) { 37 ListNode* front_remove = head; 38 int cnt_n = 0; 39 ListNode* cur_node = head; 40 while (cur_node != NULL) { 41 if (cnt_n > n) front_remove = front_remove -> next; 42 else cnt_n++; 43 cur_node = cur_node -> next; 44 } 45 if (cnt_n > n) front_remove -> next = front_remove -> next -> next; 46 else if (cnt_n == n) head = head -> next; 47 return head; 48 } 49 }; 50 // 思路：一般解法；或者新建头节点。
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
1 #include <string> 2 #include <cstdio> 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 8 struct ListNode { 9 int val; 10 ListNode *next; 11 ListNode(int x) : val(x), next(NULL) {} 12 }; 13 14 class Solution { 15 public: 16 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 17 ListNode* res = new ListNode(0); 18 ListNode* ptr = res; 19 while (l1 != NULL && l2 != NULL) { 20 if (l1 -> val < l2 -> val) { 21 ptr -> next = l1; 22 l1 = l1 -> next; 23 } else { 24 ptr -> next = l2; 25 l2 = l2 -> next; 26 } 27 ptr = ptr -> next; 28 } 29 if (l1 == NULL) ptr -> next = l2; 30 if (l2 == NULL) ptr -> next = l1; 31 return res -> next; 32 } 33 34 35 ListNode *mergeTwoLists_recursive(ListNode *l1, ListNode *l2) { 36 if(l1 == NULL) return l2; 37 if(l2 == NULL) return l1; 38 39 if(l1->val < l2->val) { 40 l1->next = mergeTwoLists_recursive(l1->next, l2); 41 return l1; 42 } else { 43 l2->next = mergeTwoLists_recursive(l2->next, l1); 44 return l2; 45 } 46 } 47 }; 48 // 思路：递归和非递归
23. Merge k Sorted Lists
不熟练
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 struct compare { 8 bool operator()(const ListNode* l, const ListNode* r) { 9 return l->val > r->val; 10 } 11 }; 12 13 class Solution { 14 public: 15 ListNode* mergeKLists(vector<ListNode*>& lists) { 16 priority_queue<ListNode*, vector<ListNode*>, compare> q; 17 for (int i = 0; i < lists.size(); i++) { // for (auto i : lists) 18 if (lists[i]) q.push(lists[i]); 19 } 20 if(q.empty()) return NULL; 21 ListNode* result = q.top(); 22 ListNode* ptr = q.top(); 23 q.pop(); 24 if (result -> next) q.push(result -> next); 25 while (!q.empty()) { 26 ptr -> next = q.top(); 27 q.pop(); 28 ptr = ptr -> next; 29 if (ptr -> next) q.push(ptr -> next); 30 } 31 return result; 32 } 33 }; 34 // 思路：优先队列
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* swapPairs(ListNode* head) { 10 if (head == NULL || head -> next == NULL) return head; 11 ListNode* result = new ListNode(0); 12 ListNode* last = result; 13 ListNode* temp = head; 14 while (temp != NULL && temp -> next != NULL) { 15 // cout << temp -> val << endl; 16 last -> next = temp -> next; 17 last = temp; 18 temp = temp -> next -> next; 19 last -> next -> next = last; 20 } 21 last -> next = temp; 22 return result -> next; 23 } 24 25 /*********没看懂****************/ 26 ListNode* swapPairs2(ListNode* head) { 27 ListNode **pp = &head, *a, *b; 28 while ((a = *pp) && (b = a->next)) { 29 a->next = b->next; 30 b->next = a; 31 *pp = b; 32 pp = &(a->next); 33 } 34 return head; 35 } 36 /************************/ 37 };
25. Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* reverseKGroup_recursive(ListNode* head, int k) { 10 //**************待解决************// 11 12 13 } 14 15 ListNode* reverseKGroup(ListNode* head, int k) { 16 if (head == NULL || k < 2) return head; 17 ListNode* last = new ListNode(0); 18 ListNode* result = last; 19 ListNode* first; 20 ListNode* second = head; 21 ListNode* third = head -> next; 22 ListNode* tmp = head; 23 ListNode* cur = head; 24 int cnt = 0; 25 while (1) { 26 while (cnt < k && cur != NULL && third != NULL) { 27 cur = cur -> next; 28 ++cnt; 29 } 30 if (cnt < k) { 31 last -> next = second; 32 return result -> next; 33 } 34 while (--cnt) { 35 first = second; 36 // cout << first -> val << " "; 37 second = third; 38 third = second -> next; 39 second -> next = first; 40 } 41 last -> next = second; 42 last = tmp; 43 tmp = cur; 44 first = second; 45 second = third; 46 if (third != NULL) third = second -> next; 47 } 48 return result -> next; 49 } 50 };
61. Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
1 // 忽略了k大于size的情况 2 class Solution { 3 public: 4 ListNode* rotateRight(ListNode* head, int k) { 5 if (head == NULL) return head; 6 ListNode* tail = head; 7 int cnt = 1; 8 while (tail -> next != NULL) { 9 tail = tail -> next; 10 ++cnt; 11 } 12 tail -> next = head; 13 if (k%cnt > 0) { 14 for (int i = cnt - k%cnt; i > 0; --i) tail = tail -> next; 15 } 16 head = tail -> next; 17 tail -> next = NULL; 18 return head; 19 } 20 }; 21 // 思路：连接头尾，再拆开
82. Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* deleteDuplicates(ListNode* head) { 10 if (head == NULL) return head; 11 ListNode* last = new ListNode(0); 12 last -> next = head; 13 ListNode* ptr = head; 14 ListNode* newhead = last; 15 while (ptr != NULL) { 16 if (ptr -> next == NULL || ptr -> val != ptr -> next -> val) { 17 if (last -> next != ptr) last -> next = ptr -> next; 18 else last = last -> next; 19 } 20 if (ptr != NULL) ptr = ptr -> next; 21 } 22 return newhead -> next; 23 } 24 };
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* deleteDuplicates(ListNode* head) { 10 ListNode* last = new ListNode(0); 11 last -> next = head; 12 ListNode* ptr = head; 13 head = last; 14 while (ptr != NULL) { 15 if (ptr -> next == NULL || ptr -> val != ptr -> next -> val) { 16 if (last -> next != ptr) last -> next = ptr; 17 last = ptr; 18 } 19 ptr = ptr -> next; 20 } 21 return head -> next; 22 } 23 };
86. Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* partition(ListNode* head, int x) { 10 ListNode left(0), right(0); 11 ListNode *p_left = &left, *p_right = &right; 12 while (head) { 13 if (head -> val < x) p_left = p_left -> next = head; 14 else p_right = p_right -> next = head; 15 head = head -> next; 16 } 17 p_right -> next = NULL; 18 p_left -> next = right.next; 19 return left.next; 20 } 21 };
92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
1 class Solution { 2 public: 3 ListNode* reverseBetween(ListNode* head, int m, int n) { 4 ListNode* new_head = new ListNode(0); 5 new_head -> next = head; 6 ListNode* first = new_head; 7 int k = m; 8 while (--k) first = first -> next; 9 ListNode* second = first -> next; 10 ListNode* third = second -> next; 11 while (n-- > m) { 12 second -> next = third -> next; 13 third -> next = first -> next; 14 first -> next = third; 15 third = second -> next; 16 } 17 return new_head -> next; 18 } 19 }; 20 21 // 我的实现 22 class Solution2 { 23 public: 24 ListNode* reverseBetween(ListNode* head, int m, int n) { 25 ListNode* new_head = new ListNode(0); 26 new_head -> next = head; 27 ListNode* left = new_head; 28 int k = m; 29 while (--k) left = left -> next; 30 ListNode* first = left -> next; 31 ListNode* right = first; 32 ListNode* second = first -> next; 33 ListNode* third; 34 while (n-- > m) { 35 third = second -> next; 36 second -> next = first; 37 first = second; 38 second = third; 39 } 40 left -> next = first; 41 right -> next = second; 42 return new_head -> next; 43 } 44 };
109. Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 8 struct TreeNode { 9 int val; 10 TreeNode *left; 11 TreeNode *right; 12 TreeNode(int x) : val(x), left(NULL), right(NULL) {} 13 }; 14 15 16 class Solution { 17 public: 18 TreeNode* sortedListToBST(ListNode* head) { 19 if (head == NULL) return head; 20 return func(head, NULL); 21 } 22 TreeNode* func(ListNode* head, ListNode* tail) { 23 if (head == tail) return NULL; 24 ListNode* middle = head; 25 ListNode* ptail = head; 26 while (ptail != tail && ptail -> next != tail) { 27 middle = middle -> next; 28 ptail = ptail -> next -> next; 29 } 30 TreeNode* add = new TreeNode(middle -> val); 31 add -> left = func(head, middle); 32 add -> right = func(middle -> next, tail); 33 return add; 34 } 35 }; 36 37 // java reference-1 38 public class Solution { 39 public TreeNode sortedListToBST(ListNode head) { 40 if(head==null) return null; 41 return toBST(head,null); 42 } 43 public TreeNode toBST(ListNode head, ListNode tail){ 44 ListNode slow = head; 45 ListNode fast = head; 46 if(head==tail) return null; 47 48 while(fast!=tail&&fast.next!=tail){ 49 fast = fast.next.next; 50 slow = slow.next; 51 } 52 TreeNode thead = new TreeNode(slow.val); 53 thead.left = toBST(head,slow); 54 thead.right = toBST(slow.next,tail); 55 return thead; 56 } 57 58 59 // java reference-2 60 private ListNode node; 61 62 public TreeNode sortedListToBST(ListNode head) { 63 if(head == null){ 64 return null; 65 } 66 67 int size = 0; 68 ListNode runner = head; 69 node = head; 70 71 while(runner != null){ 72 runner = runner.next; 73 size ++; 74 } 75 76 return inorderHelper(0, size - 1); 77 } 78 79 public TreeNode inorderHelper(int start, int end){ 80 if(start > end){ 81 return null; 82 } 83 84 int mid = start + (end - start) / 2; 85 TreeNode left = inorderHelper(start, mid - 1); 86 87 TreeNode treenode = new TreeNode(node.val); 88 treenode.left = left; 89 node = node.next; 90 91 TreeNode right = inorderHelper(mid + 1, end); 92 treenode.right = right; 93 94 return treenode; 95 }
138. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
1 struct RandomListNode { 2 int label; 3 RandomListNode *next, *random; 4 RandomListNode(int x) : label(x), next(NULL), random(NULL) {} 5 }; 6 7 // 错误原因：1漏掉；2指向空指针的情况；3不能两个while，必须先处理掉random 8 class Solution { 9 public: 10 RandomListNode *copyRandomList(RandomListNode *head) { 11 if (head == NULL) return NULL; //@1 12 RandomListNode* ptr = head; 13 while (ptr != NULL) { 14 RandomListNode* new_node = new RandomListNode(ptr -> label); 15 new_node -> next = ptr ->next; 16 new_node -> random = ptr -> random; 17 ptr -> next = new_node; 18 ptr = new_node -> next; 19 } 20 ptr = head; 21 while (ptr) { 22 ptr = ptr -> next; 23 if (ptr -> random) ptr -> random = ptr -> random -> next; // @2 24 ptr = ptr -> next; 25 } 26 RandomListNode* origin = head; 27 RandomListNode* new_head = new RandomListNode(0); 28 ptr = new_head; 29 while (origin) { 30 ptr -> next = origin -> next; 31 ptr = ptr -> next; 32 origin -> next = ptr -> next; 33 origin = origin -> next; 34 } 35 return new_head -> next; 36 } 37 };
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 错误原因，while条件不全 8 class Solution { 9 public: 10 bool hasCycle(ListNode *head) { 11 if (head == NULL) return 0; 12 ListNode* fast = head, *slow = head; 13 while (fast && fast -> next && fast -> next -> next) { 14 fast = fast -> next -> next; 15 slow = slow -> next; 16 if (fast == slow) return 1; 17 } 18 return 0; 19 } 20 };
142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 没搞太懂 8 class Solution { 9 public: 10 ListNode *detectCycle(ListNode *head) { 11 if (head == NULL || head -> next == NULL) return NULL; 12 ListNode* slow = head; 13 ListNode* fast = head; 14 ListNode* meet_point = head; 15 while (fast -> next != NULL && fast -> next -> next != NULL) { 16 slow = slow -> next; 17 fast = fast -> next -> next; 18 if (slow == fast) { 19 while (slow != meet_point) { 20 slow = slow -> next; 21 meet_point = meet_point -> next; 22 } 23 return meet_point; 24 } 25 } 26 return NULL; 27 } 28 };
143. Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
1 class Solution { 2 public: 3 void reorderList(ListNode* head) { 4 if (head == NULL || head -> next == NULL || head -> next -> next == NULL) return; //@1 5 ListNode* fast = head; 6 ListNode* slow = head; 7 while (fast -> next && fast -> next -> next) { 8 slow = slow -> next; 9 fast = fast -> next -> next; 10 } 11 12 ListNode* first = slow -> next; 13 slow -> next = NULL; //@2 14 ListNode* second = first -> next; 15 ListNode* third; 16 first -> next = NULL; 17 while (second) { 18 third = second -> next; 19 second -> next = first; 20 first = second; 21 second = third; 22 } 23 24 second = first; 25 first = head; 26 third = first -> next; 27 while (second) { 28 first -> next = second; 29 first = second; 30 second = third; 31 third = first -> next; 32 } 33 return; 34 } 35 };
147. Insertion Sort List
Sort a linked list using insertion sort.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 错误原因：@1写成了:second = head; 8 class Solution { 9 public: 10 ListNode* insertionSortList(ListNode* head) { 11 if (head == NULL || head -> next == NULL) return head; 12 ListNode* new_head = new ListNode(0); 13 new_head -> next = head; 14 ListNode* first = new_head; 15 ListNode* second = head; 16 ListNode* third = second -> next; 17 second -> next = NULL; 18 while (third != NULL) { 19 while (second != NULL && second -> val < third -> val) { 20 first = second; 21 second = second -> next; 22 } 23 first -> next = third; 24 third = third -> next; 25 first -> next -> next = second; 26 first = new_head; 27 second = first -> next; // @1 28 } 29 return new_head -> next; 30 } 31 };
148. Sort List
Sort a linked list in O(n log n) time using constant space complexity.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 错误原因：@1写成了|| 8 class Solution { 9 public: 10 ListNode* sortList(ListNode* head) { 11 if (head == NULL || head -> next == NULL) return head; 12 ListNode* slow = head, *fast = head; 13 ListNode* right, *left; 14 while (fast -> next != NULL && fast -> next -> next != NULL) { 15 slow = slow -> next; 16 fast = fast -> next -> next; 17 } 18 fast = slow -> next; 19 slow -> next = NULL; 20 left = sortList(head); 21 right = sortList(fast); 22 ListNode* merge_list = new ListNode(0); 23 ListNode* new_head = merge_list; 24 while (left && right) { //@! 25 if (left -> val < right -> val) { 26 merge_list -> next = left; 27 merge_list = left; 28 left = left -> next; 29 } 30 else { 31 merge_list -> next = right; 32 merge_list = right; 33 right = right -> next; 34 } 35 } 36 merge_list -> next = left ? left : right; 37 return new_head -> next; 38 } 39 };
160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // ac 8 class Solution { 9 public: 10 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 11 if (headA == NULL || headB == NULL) return NULL; 12 ListNode* nodeA = headA; 13 ListNode* nodeB = headB; 14 while (nodeA != nodeB) { 15 nodeA = nodeA == NULL ? headB : nodeA -> next; 16 nodeB = nodeB == NULL ? headA : nodeB -> next; 17 } 18 return nodeA; 19 } 20 }; 21 22 // 思路：遍历两次，第一次用来计算长度的差值
203. Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // ac 8 class Solution { 9 public: 10 ListNode* removeElements(ListNode* head, int val) { 11 ListNode* new_head = new ListNode(0); 12 new_head -> next = head; 13 ListNode* pre = head; 14 ListNode* last = new_head; 15 while (pre) { 16 if (pre -> val == val) { 17 last -> next = pre -> next; 18 pre = last -> next; 19 } 20 else { 21 last = pre; 22 pre = pre -> next; 23 } 24 } 25 return new_head -> next; 26 } 27 }; 28 29 // 递归 30 public ListNode removeElements(ListNode head, int val) { 31 if (head == null) return null; 32 head.next = removeElements(head.next, val); 33 return head.val == val ? head.next : head; 34 }
206. Reverse Linked List
Reverse a singly linked list.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 错误原因：@1：少了尾部赋值 8 class Solution { 9 public: 10 ListNode* reverseList(ListNode* head) { 11 if (head == NULL || head -> next == NULL) return head; 12 ListNode* new_head = reverseList(head -> next); 13 head -> next -> next = head; 14 head -> next = NULL; //@1 15 return new_head; 16 } 17 };
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
do it in O(n) time and O(1) space
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // 错误：低级错误。。。 8 class Solution { 9 public: 10 bool isPalindrome(ListNode* head) { 11 ListNode* new_head = new ListNode(0); 12 new_head -> next = head; 13 ListNode* fast = new_head; 14 ListNode* slow = new_head; 15 while (fast -> next && fast -> next -> next) { 16 slow = slow -> next; 17 fast = fast -> next -> next; //@1 18 } 19 fast = reverseList(slow -> next); 20 slow -> next = NULL; 21 slow = head; 22 while (slow) { 23 if (fast -> val != slow -> val) return false; 24 fast = fast -> next; 25 slow = slow -> next; 26 } 27 return true; 28 } 29 ListNode* reverseList(ListNode* head) { 30 if (head == NULL || head -> next == NULL) return head; 31 ListNode* first = NULL; 32 ListNode* second = head; 33 ListNode* third; //@2 34 while (second) { 35 third = second -> next; 36 second -> next = first; 37 first = second; 38 second = third; 39 } 40 return first; 41 } 42 };
237. Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution1 { 8 public: 9 void deleteNode(ListNode* node) { 10 auto next = node -> next; 11 *node = *(node -> next); 12 delete next; 13 } 14 };
328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // ac 8 class Solution { 9 public: 10 ListNode* oddEvenList(ListNode* head) { 11 if (head == NULL || head -> next == NULL || head -> next -> next == NULL) return head; 12 ListNode* odd = head; 13 ListNode* even = head -> next; 14 ListNode* even_head = even; 15 while (odd -> next && odd -> next -> next) { 16 odd = odd -> next = odd -> next -> next; 17 even = even -> next = even -> next -> next; 18 } 19 odd -> next = even_head; 20 return head; 21 } 22 }; 23 // 思路：分别计算奇偶链表，再合并
445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 // ac 8 class Solution { 9 public: 10 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 11 stack<int> l1_stack; 12 stack<int> l2_stack; 13 int sum = 0; 14 ListNode* res = NULL; 15 for (; l1 != NULL; l1 = l1 -> next) l1_stack.push(l1 -> val); 16 for (; l2 != NULL; l2 = l2 -> next) l2_stack.push(l2 -> val); 17 while (!l1_stack.empty() || !l2_stack.empty()) { 18 if (!l1_stack.empty()) { 19 sum += l1_stack.top(); 20 l1_stack.pop(); 21 } 22 if (!l2_stack.empty()) { 23 sum += l2_stack.top(); 24 l2_stack.pop(); 25 } 26 ListNode* node = new ListNode(sum%10); 27 node -> next = res; 28 res = node; 29 sum = sum/10; 30 } 31 if (sum) { 32 ListNode* node = new ListNode(sum); 33 node -> next = res; 34 res = node; 35 } 36 return res; 37 } 38 }; 39 // 思路：使用栈
Array
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 unordered_map<int, int> hash; 5 vector<int> result; 6 for (int i = 0; i < nums.size(); i++) { 7 if (hash.find(target - nums[i]) != hash.end()) { 8 result.push_back(hash[target - nums[i]]); 9 result.push_back(i); 10 return result; 11 } 12 hash[nums[i]] = i; 13 } 14 return result; 15 } 16 };
leetcode笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。