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);
*/