第一天刷题。一个平实的开始，希望能坚持下来，不求波涛汹涌，大浪淘沙，但求静水流深，川流不息。
先学习双指针。题目方向分为两个：链表和数组。
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
文章目录
链表中的双指针
第一道：21.合并两个有序链表
思路一：申请第三个链表的空间，拷贝两个链表中较小的一个。
代码v1.0：
class Solution {
public:
bool comp(ListNode* l1, ListNode* l2){
if(l1->val > l2->val) return true;
else return false;
}
bool Empty_Judge(ListNode* l){
if(l->val==0) return true;
else return false;
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(Empty_Judge(list1)) return list2;
if(Empty_Judge(list2)) return list1;
ListNode* list ;
ListNode* head = list;
while(list1!=nullptr&&list2!=nullptr)
{
list = new ListNode;
if(comp(list1,list2)){
list->val = list2->val;
list = list->next;
list2 = list2->next;
}
else{
list->val = list1->val;
list = list->next;
list1 = list1->next;
}
}
while(list1!=nullptr){
list = new ListNode(list1->val);
list=list->next;
list1=list1->next;
}
while(list2!=nullptr){
list = new ListNode(list2->val);
list=list->next;
list2=list2->next;
}
return head;
}
};
问题：返回的 head 没有任何数值。
解决：
链表到下一个结点前需要空间，否则指向NULL就是野指针，也就不可能连上。
代码开始，head 指向了没有初始化的 list ，即指向一个（指向null的）野指针，它自己也变成了野指针。如果初始化工作做好，不解决后续连接过程的“先申请空间，再连接”，就会只有一个数据。
条件判断分不清 NULL 、nullptr 及其背后的 true 、false，造成代码冗余。
Empty_judge 和 comp 函数是完完全全的多余代码，因为本可以直接在原代码中判断。
代码V2.0：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
if(!list2) return list1;
ListNode* list = new ListNode ;
ListNode* head = list;
while(list1&&list2)
{
if(list1->val > list2->val){
list->val = list2->val;
list2 = list2->next;
}
else{
list->val = list1->val;
list1 = list1->next;
}
list->next = new ListNode;
list = list->next;
}
while(list1)
{
list ->val = list1 -> val;
if(list1->next) list->next = new ListNode;
list=list->next;
list1=list1->next;
}
while(list2)
{
list ->val = list2 -> val;
if(list2->next) list->next = new ListNode;
list=list->next;
list2=list2->next;
}
return head;
}
};
规避了野指针问题和相对的代码冗余问题。
思路二：在两个指针现有的空间上，只做穿针引线的工作（连接起来）
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2; //可以省略
if(!list2) return list1;
ListNode* list = new ListNode;
ListNode* head = list;
while(list1&&list2)
{
if(list1->val > list2->val){
list -> next = list2;
list = list2; //这里可以配合下面简化
list2 = list2->next;
}
else{
list -> next = list1;
list = list1; //简化
list1 = list1->next;
//list = list->next
}
}
list -> next = list1 ? list1 : list2;
return head -> next;
}
问题：
- 开始的判断是否为空可以省略。
- while 中出现重复点（只是需要一点点直觉）
解决：
看思路三。
**思路三：**labuladong ，虚拟头结点值得注意。整体与思路二没什么区别。
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是
dummy节点。你可以试试，如果不使用dummy虚拟节点，代码会复杂很多，而有了dummy节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。
拓展：
思路四：递归
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
类似汉诺塔的思路。
第二道：分割链表
V1.0
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
//初始化
ListNode* tail = head;
while(tail->val < x ) tail=tail->next;
ListNode* temp = tail;
ListNode* maxdot = tail;//大于值开始的结点
while(head->val > x) head = head->next;
tail = head; //小于值开始的结点
while(temp)
{
//<x
if(temp->val < x){ //如果是小于值结点
tail ->next = temp;
tail = tail->next;
}
//>x
if(temp->val >x &&temp->next->val < x ){
tail->next = temp->next;
if(temp->next->next) temp->next = temp->next->next;
else {
tail->next = temp->next;
temp->next = nullptr;
break;
}
}
temp = temp->next;
}
tail->next = maxdot;
return head;
}
};
现在思路也不是很清晰
思路二：双头结点
ListNode partition(ListNode head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode* dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode* dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode* p1 = dummy1, p2 = dummy2;
// p 负责遍历原链表，类似合并两个有序链表的逻辑
// 这里是将一个链表分解成两个链表
ListNode* p = head;
while (p != null) {
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
p1.next = p;
p1 = p1.next;
}
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;
}
// 连接两个链表
p1.next = dummy2.next;
return dummy1.next;
}
创建两个头结点，先断开，后连接。
思路三：递归
class Solution {
public:
ListNode* small = nullptr;
pair<ListNode*, ListNode*> helper(ListNode* head, int x) {
if (head == nullptr) return make_pair(nullptr, nullptr);
if (head->val < x) small = head;
pair<ListNode*, ListNode*> next = helper(head->next, x);
if (head->val < x) {
head->next = next.first;
next.first = head;
}
else {
head->next = next.second;
next.second = head;
}
return next;
}
ListNode* partition(ListNode* head, int x) {
pair<ListNode*, ListNode*> nodes = helper(head, x);
if (nodes.first) {
small->next = nodes.second;
return nodes.first;
}
else {
return nodes.second;
}
}
};
大多数链表题递归的时候可以无脑写一句，然后只要让思路从后向前进行就可以了。
cppListNode* node = func(head->next); // func为递归函数
这里返回值选择了两个pair，first保存小于x的结点，second保存大于x的结点。
思路四:原地连接
// 1 4 3 2 5 2
struct ListNode* partition(struct ListNode* head, int x){
if(!head || !head->next){
return head;
}
struct ListNode *p = head, *q = head, *temp = NULL;
if(p->val < x){
while(p->next->val < x){//此循环让 p 到达最远小值 1
p = p->next;
if(p->next == NULL){
return head;
}
}
q = p->next; //让 q 到达最近大值 4
}
else{
p = NULL;
}
while(q->next){ //q存在下一个结点
if(q->next->val < x){ //如果最近大值下一个为小值
temp = q->next; //temp为小值了
q->next = temp->next;//跳过小值
if(p == NULL){ //如果起始值为大值（即p 为空情况）
temp->next = head; //头插法：第一个插入的小值连接起始大值
head = temp;
p = head;
}
else{//起始值小值（存在了）
temp->next = p->next; //头插法：小值后
p->next = temp;
p = temp;
}
}
else{ //为大值就串下去
q = q->next;
}
}
return head;
}
p指针指向小于 x 的值，p == null 就连接第一个大于x的值，p!=null 就按顺序进行尾插法；
(只是 p 的"尾"是 q 的"头")
q指针指向大于 x 的值，初始是第一个大于x的值， 尾插法依次往后放;
temp 服务于p的尾插法，作为中间变量。
（q 尾插循环的前面，是p,q 的初始化工作，分别指定小于x值的尾端 和 大于x值的尾端）
第三道：合并K个升序链表
思路一：遍历合并两个链表到第一个链表中去
class Solution {
public:
ListNode* merge(ListNode* list1,ListNode* list2) //这里和合并有序链表的code一模一样
{...}
ListNode* mergeKLists(vector<ListNode*>& lists) {//遍历合并
if(lists.empty()) return nullptr;
vector<ListNode*>::iterator it = lists.begin();
vector<ListNode*>::iterator next = lists.begin()+1;
for(;next!=lists.end();next++){
*it = merge(*it,*next);
}
return *it;
}
};
**思路二：**labladong ：配合优先队列的二叉堆，获取最小k结点
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode*> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
思路三：分治递归
class Solution {
public ListNode mergeKLists(ListNode[] lists){
if(lists.length == 0)
return null;
if(lists.length == 1)
return lists[0];
if(lists.length == 2){
return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.length/2;
ListNode[] l1 = new ListNode[mid];
for(int i = 0; i < mid; i++){
l1[i] = lists[i];
}
ListNode[] l2 = new ListNode[lists.length-mid];
for(int i = mid,j=0; i < lists.length; i++,j++){
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
}
思路四：STL中的优先队列
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto head = ListNode(0);
auto comp = [](ListNode* const &a, ListNode* const &b){return a->val > b->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);
for (auto &h : lists) if (h != nullptr) q.push(h);
auto p = &head;
while (!q.empty()) {
p->next = q.top();
p = p->next;
q.pop();
if (p->next != nullptr) q.push(p->next);
}
return head.next;
}
};
第四道：单链表的倒数第 k 个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(n==0||!head) return head; //0元素 或 不动
if(!head->next) return NULL; //1元素 且 动
ListNode* fformer = head;
ListNode* former = head;
ListNode* latter = head;
while(--n>0) latter = latter->next;
while(latter->next)
{
if(former!=head) fformer = fformer->next;
latter = latter -> next;
former = former -> next;
}
//1元素
if(former == fformer) head = former->next; //2元素
else fformer->next = former->next; //3+元素
return head;
第五道：链表的中间结点
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast->next)
{
fast = fast->next;
if(fast->next) fast=fast->next;
slow = slow->next;
}
return slow;
}
第六道：相交链表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/**
定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
**/
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
// 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
while(pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
这个赋值和
？条件判断 的配合非常有趣。简短的 if 语句可用 ？来代替。
思路二：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0, lenB = 0;
// 计算两条链表的长度
for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
lenA++;
}
for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
lenB++;
}
// 让 p1 和 p2 到达尾部的距离相同
ListNode p1 = headA, p2 = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
p1 = p1.next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
p2 = p2.next;
}
}
// 看两个指针是否会相同，p1 == p2 时有两种情况：
// 1、要么是两条链表不相交，他俩同时走到尾部空指针
// 2、要么是两条链表相交，他俩走到两条链表的相交点
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
第七道：判断是否为环形链表
boolean hasCycle(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇，说明含有环
if (slow == fast) {
return true;
}
}
// 不包含环
return false;
}
不解释
第八道：找到环形链表的起点
流程起始同上，先让快慢指针相遇。
设相遇点距离头结点为 k ,即慢指针的路程。快指针速度是慢指针二倍，路程即 k+k=2k
设环形起点距离相遇点为 m , 则慢指针距离起点
k-m。巧合的是，相遇点指针不断向后走，距离起点同样为k-m。所以让其中任意一个指针回到起点，经过
k-m位移，另一个指针就会到达环形链表起点。
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
数组中的双指针
在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧。
第一道： 删除有序数组中的重复项
基本的快慢双指针。
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
大同小异的一个链表题：
删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/)
struct ListNode* deleteDuplicates(struct ListNode* head){
typedef struct ListNode ListNode;
if(!head) return head;
ListNode* slow = head;
ListNode* fast = head;
while(fast)
{
if(fast->val!=slow->val)
{
slow=slow->next;
slow->val=fast->val;
}
fast=fast->next;
}
slow->next = NULL;
return head;
第二道：移除元素
左右指针：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = nums.size() - 1;
for (int i = 0; i <= j; i++) {
if (nums[i] == val) {
swap(nums[i--], nums[j--]);
}
}
return j + 1;
}
};
快慢指针：
while(fast<numsSize)
{
if(nums[fast]!=val)
{
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
扩展：保留重复k个元素的基础上删除多余元素
class Solution { public: int work(vector<int>& nums, int k) { int len = 0; for(auto num : nums) if(len < k || nums[len-k] != num) nums[len++] = num; return len; } int removeDuplicates(vector<int>& nums) { return work(nums, 2); } };
第三道:移动零
v1.0
void moveZeroes(vector<int>& nums) {
int fast = 0,slow=0;
while(fast<nums.size())
{
if(nums[fast]!=0){
nums[slow++] = nums[fast];
}
fast++;
}
while(slow<fast){
nums[slow++]=0;
}
}
v2.0
int left = 0;
int right = 0;
while(right < nums.size())
{
if(nums[right])
{
swap(nums[left], nums[right]);
left++;
}
right++;
}
遇到非0直接交换就可以
第四道：最长回文子串
string longestPalindrome(string s) {
string res = "";
for(int i=0;i<s.size();i++)
{
string s1=palindrome(s,i,i);
string s2=palindrome(s,i,i+1);
res = s1.size()>res.size()?s1:res;
res = s2.size()>res.size()?s2:res;
}
return res;
}
string palindrome(string s,int l,int r)
{
while(l>=0&&r<s.size()&&s[l]==s[r])
{
l--;
r++;
};
return s.substr(l+1,r-l-1);
}
左右指针，向两侧扩散。
遍历中心点。
中心点分奇数、偶数两种情况，依次比较即可。
