原题:
思路:
采用双指针,找到start - 1和 end + 1 的位置,然后进行类似于链表插入的操作即可,解决本问题的重点在于能够准确找到对应的节点。
获新:
nullptr 在定义指针的时候,为了避免出现野指针的情况,一般会在定义指针的时候直接完成初始化,nullptr就是用来完成空指针初始化的。
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
// 考虑边缘情况,一般都会设置一个虚拟节点
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = list1;
// 因为我们要找的是a-1个点,起点是dummy
ListNode* head = dummyNode;
// 第a-1个结点
ListNode* preNode = nullptr;
// 第b+1个结点
ListNode* postNode = nullptr;
while (a > 0)
{
--a;
--b; //因为利用head控制当前在list1中的位置,所以最后的b就是当前位置与end位置的距离
head = head->next;
}
preNode = head;
while (b >= 0)
{
--b;
head = head->next;
}
// 到了b个结点,需要是下一个
postNode = head->next;
// 找到list2的最后一个结点
preNode->next = list2;
while (list2->next != nullptr)
{
list2 = list2->next;
}
list2->next = postNode;
return dummyNode->next;
}
};
部分注释:
1.此题涉及节点删除边界问题,所以设置一个虚拟节点。
2.定义三个指针,head指向虚拟节点,preNode 用来记录start,postNode用来记录end。
3.之所以在a--的同时会b--,是因为控制的是head指针的指向,更新后的b代表当前位置与end位置的距离,接下来可以通过较少的次数找到end的节点。