LeetCode(一)链表专题

19.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *first = dummy, *second = dummy; for(int i = 0; i < n; i ++) first = first->next;//先把first向后移n位 while(first->next) { first = first->next; second = second->next; } second->next = second->next->next;//删除节点 return dummy->next; } };

83.删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2 输出: 1->2

示例 2:

输入: 1->1->2->3->3 输出: 1->2->3

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head) return NULL;//链表为空 返回NULL ListNode *first, *second; first = second = head; while(first) { if(first->val != second->val)//不等 加入second { second->next = first; second = first; } first = first->next; } second->next = NULL; return head; } };

206.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { //迭代O（n） if(!head || !head->next) return head; ListNode *pre = NULL; ListNode *cur = head; while(cur) { ListNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } }; /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { //递归O（n） if(!head || !head->next) return head; ListNode * p = reverseList(head->next);//翻转后尾节点是头结点 head->next->next = head;//翻转后head->next 是尾节点 head->next = NULL; return p; } };

92.反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if(n == m) return head; ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *b = dummy; for(int i = 0; i < m -1; i++) b = b->next; ListNode *a = b; b = b->next; ListNode *c = b->next; for(int i = 0;i < n - m;i++) { ListNode *next = c->next; c->next = b; b = c; c = next; } ListNode *mp = a->next; ListNode *np = b; a->next = np; mp->next = c; return dummy->next; } };

61.旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head) return NULL; int n = 0; ListNode *tail; for(ListNode *p = head; p; p = p->next) { n++; tail = p; } k %= n; //k有可能很大 if(!k) return head; //k=0 ListNode *a = head; for(int i = 0; i < n - k - 1; i++) { a = a->next; } ListNode *b = a->next; tail->next = head; a->next = NULL; return b; } };

143.重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode* head) { int n = 0; for(ListNode *p = head; p; p = p->next) n++; if(n <= 2) return; ListNode *mid = head; for(int i = 0; i < (n + 1) / 2 - 1; i++) mid = mid->next; ListNode *a = mid->next, *b = a->next; mid->next = 0, a->next = 0; while(b) //翻转后半段 { ListNode *next = b->next; b->next = a; a = b; b = next; } b = head; //指向前半段头结点 while(a) { ListNode *next = a->next; //a后半段头结点 a->next = b->next, b->next = a; b = b->next->next; a = next; } } };

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode * dummy = new ListNode(-1); ListNode * cur = dummy; while(l1 != NULL && l2 != NULL) { if(l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = (l1 == NULL ? l2 : l1); return dummy->next; } };

160.相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

/** * 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) { if(!a) a = headB;//如果a为空 指向b开头走 else a = a->next; if(!b) b = headA; else b = b->next; } return a; } };

141.环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

/** * 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) { if(!head || !head->next) return NULL; ListNode *fast = head->next, *slow = head; while(fast && slow) { if(fast == slow) return true; fast = fast->next; slow = slow->next; if(fast) fast = fast->next; } return false; } };

142.环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。

进阶： 你是否可以不用额外空间解决此题？

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head || !head->next) return NULL; ListNode *fast = head, *slow = head; while(fast && slow) { fast = fast->next; slow = slow->next; if(fast) fast = fast->next; else return 0; if(fast == slow) { slow = head; while(fast != slow) { fast = fast->next; slow = slow->next; } return slow; } } return 0; } };

147.对链表进行插入排序

对链表进行插入排序。

插入排序算法：

1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 3.重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3 输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0 输出: -1->0->3->4->5

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* insertionSortList(ListNode* head) { ListNode *dummy = new ListNode(-1); while(head) { ListNode *next = head->next; ListNode *p = dummy; while(p->next && p->next->val <= head->val) p = p->next; head->next = p->next; p->next = head; head =next; } return dummy->next; } };

LeetCode 138. Copy List with Random Pointer

题目描述 给定一个单链表，链表中的每个节点包含一个额外的指针，随机指向链表中的其它节点或者指向 null。 请复制整个链表，并返回新链表的头结点。

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node() {} Node(int _val, Node* _next, Node* _random) { val = _val; next = _next; random = _random; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head == NULL) return NULL; Node* p = head, *tempP; //1.扫描链表，复制所有节点 while(p) { tempP = new Node(p->val,p->next,p->random); //将这个复制的节点插入到复制源的后面 tempP->next = p->next; p->next = tempP; p = p->next->next;//移动必须是移动两个一次，因为刚刚在后面插入了一个复制的节点 } //2.再次扫描链表，复制random节点 p = head; while(p) { if(p->random) { //pHead->next是pHead的复制，所以pHead->random->next的复制是pHead->random p->next->random = p->random->next; } else p->next->random = NULL; p = p->next->next; } //3.将两个链表拆开 p =head; Node* copyHead = p->next; while(p) { tempP = p->next; p->next = p->next->next; if(tempP->next) tempP->next = tempP->next->next; p = p->next; } return copyHead; } };

148.排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { return head == NULL ? NULL : mergeSort(head); } ListNode* mergeSort(ListNode* node) { if(node->next == NULL) return node; ListNode* fast = node, *slow = node; ListNode* breakN = node; while(fast && fast->next) { fast = fast->next->next; breakN = slow; slow = slow->next; } breakN->next = NULL; //这里分开 ListNode* l = mergeSort(node); ListNode* r = mergeSort(slow); return mergeTwoLists(l , r); } ListNode* mergeTwoLists(ListNode* l1,ListNode* l2) { ListNode* temp_head = new ListNode(0); ListNode* pre = temp_head; while(l1 && l2) { if(l1->val < l2->val) { pre->next = l1; l1 = l1->next; } else { pre->next = l2; l2 = l2->next; } pre = pre->next; } if(l1) pre->next = l1; if(l2) pre->next = l2; return temp_head->next; } };

LeetCode 146. LRU Cache

题目描述

请为LRU缓存设计一个数据结构。支持两种操作：get和set。

get(key) - 如果key在缓存中，则返回key对应的值（保证是正的）；否则返回-1； set(key, value) - 如果key在缓存中，则更新key对应的值；否则插入(key, value)，如果缓存已满，则先删除上次使用时间最老的key。

进一步： 能否使用两个操作都是 O(1)时间复杂度的算法？

样例

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 删除 key 2 cache.get(2); // 返回 -1 (没找到) cache.put(4, 4); // 删除 key 1 cache.get(1); // 返回 -1 (没找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4

class LRUCache { public: /* 使用两个双链表和一个哈希表： 第一个双链表存储未被使用的位置； 第二个双链表存储已被使用的位置，且按最近使用时间从左到右排好序； 哈希表存储key对应的链表中的节点地址； */ struct Node { int val, key; Node *left, *right; Node() : key(0), val(0), left(NULL), right(NULL) {} }; Node *head_used, *tail_used; //head在左侧 tail在右侧 Node *head_remains, *tail_remains; int n; unordered_map<int, Node*> hash; void delete_node(Node *p) { p->left->right = p->right;//指向左边的右边 指向右边 p->right->left = p->left; } void insert_node(Node *h, Node *p)//双向链表插入 画图模拟很简单 { p->right = h->right, h->right = p; p->left = h, p->right->left = p; } LRUCache(int capacity) { n = capacity; head_used = new Node(), tail_used = new Node(); head_remains = new Node(),tail_remains = new Node(); head_used->right = tail_used, tail_used->left = head_used; head_remains->right = tail_remains, tail_remains->left = head_remains; for(int i = 0; i< n; i++) { Node *p = new Node(); insert_node(head_remains, p);//插入未被使用 } } int get(int key) { if(hash[key]) { Node *p = hash[key]; delete_node(p); insert_node(head_used, p);//插入已被使用 return p->val; } return -1; } void put(int key, int value) { if(hash[key]) { Node *p = hash[key]; delete_node(p); insert_node(head_used, p); p->val = value; return; } if(!n) //n = 0 内存已满 删除最近最少使用的数据 { n++; Node *p = tail_used->left; hash[p->key] = 0; delete_node(p); insert_node(head_remains, p); } //内存没满 n--; Node *p = head_remains->right; p->key = key, p->val = value, hash[key] = p; delete_node(p); insert_node(head_used, p); } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */