力扣1669 合并链表问题

原题:

力扣1669 合并链表问题

思路:

采用双指针,找到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的节点。

上一篇:[AT ZONe Energy Programming Contest] MAD TEAM


下一篇:ccf201809-1买菜