当前位置：首页 > article >正文

【LeetCode热题100】链表

article 2024/10/30 13:05:06

这篇博客记录了关于链表的几道题目：两数相加、两两交换链表中的节点、K个一组反转链表、合并K个升序链表。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* cur1 = l1,*cur2 = l2;
        ListNode* head = new ListNode; //创建哨兵位
        ListNode* tail = head; //尾指针
        int t = 0; // 记录进位 
        while(cur1 || cur2 || t) //都走完了，t可能不为0
        {
            //先加第一个链表
            if(cur1 != nullptr)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            //再加第二个链表
            if(cur2 != nullptr)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            tail->next = new ListNode(t % 10);
            tail = tail->next;
            t /= 10;
        }
        tail = head->next;
        delete head;//释放头结点
        return tail;
    }
};

题目分析：题目给出的逆序的数字，这刚好，因为求和就是从低位开始的，然后就要创建一个哨兵位头结点，比较方便，然后创建变量t用于保存相同位相加的结果，取其个位创建新节点尾插，t的十位继续和下一位的相加。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode();
        newhead->next = head;

        ListNode* prev = newhead,*cur = prev->next,*_next = cur->next,*nnext = _next->next;
        while(cur && _next)
        {
            //1.交换节点
            prev->next = _next;
            _next->next = cur;
            cur->next = nnext;
            //2.修改指针
            prev = cur;
            cur = nnext;
            if(cur) _next = cur->next;
            if(_next) nnext = _next->next;
        }  
        cur = newhead->next;
        delete newhead; 
        return cur;
    }
};

题目分析：需要创建一个哨兵位节点，并且为需要变动的节点都分配一个名字，这样比较好修改，当有偶数个时，cur为空就结束，当有奇数个时，next为空就结束。最终要释放申请的哨兵位。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        int sum = 0;
        ListNode* cur = head;
        //1.先求出要逆序多少组
        while(cur)
        {
            sum++;
            cur = cur->next;
        }
        int num = sum / k;
        //2.重复n次，长度为k的链表的逆序即可
        ListNode* newhead = new ListNode();
        ListNode* tmp = newhead; // 下一次要头插的节点
        cur = head;
        ListNode* prev = head;
        while(num--)
        {
            prev = cur; // 保存下一次头插的节点
            for(int i = 0; i < k ; i++)
            {
                ListNode* next = cur->next;
                cur->next = tmp->next;
                tmp->next = cur;
                cur = next;
            }
            tmp = prev;
        }
        //把不需要逆序的接上  
        tmp->next = cur;
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
    
};

题目分析：分为两步，第一步：先求出需要逆序多少组，第二步：重复n次，长度为k的链表的逆序即可。采用头插法逆序。也就是两层循环，第一层是循环组数次，第二层是循环k次头插。需要注意的是，第二层每次循环前，需要记录下一次要被头插的元素。

//1.解法1
class Solution 
{
    struct cmp
    {
        bool operator()(const ListNode* l1,const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        for(auto list : lists)
        {
            if(list) pq.push(list);
        }
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        while(!pq.empty())
        {
            ListNode* top = pq.top();
            pq.pop();
            prev->next = top;
            prev = prev->next;

            if(top->next) pq.push(top->next);
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};
//2.解法2
class Solution 
{
    ListNode* _mergeKLists(vector<ListNode*>& list,int left,int right)
    {
        if(left > right) return nullptr;
        if(left == right) return list[left];

        int mid = (left + right) >> 1;
        //[left,mid][mid+1,right]
        ListNode* l1 = _mergeKLists(list,left,mid);
        ListNode* l2 = _mergeKLists(list,mid+1,right);

        return MergeTwoList(l1,l2);
    }
    ListNode* MergeTwoList(ListNode* l1,ListNode* l2)
    {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

        ListNode head;
        head.next = nullptr;
        ListNode* prev = &head;
        ListNode* cur1 = l1,*cur2 = l2;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2-> val)
            {
                prev->next = cur1;
                cur1 = cur1->next;
                prev = prev->next;
            }
            else
            {
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        if(cur1) prev->next = cur1;
        if(cur2) prev->next = cur2;
        return head.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        return _mergeKLists(lists,0,lists.size()-1);
    }
};