当前位置:   article > 正文

力扣刷题记录-链表/c++_力扣 链表 c++

力扣 链表 c++

题库21题:合并两个有序链表(简单)

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 在这里插入图片描述

解法

思路:
若有空链表,则直接返回另一个链表
两个链表都不为空开始比较,哪个链表的值小,哪个就将tail指向哪个链表,并且该链表指针向后移
当某链表已经到达最后一个元素时,证明该链表的最大值也小于另一链表当前的值,tail直接指向另一链表当前位置

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr;
        ListNode *tail = nullptr;
        //若有空链表,则返回另一个链表
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        //两个链表都不为空开始比较
        //哪个链表的值小,哪个就将tail指向哪个链表,并且该链表指针向后移
       while(l1 != NULL && l2 != NULL){
           if(l1->val <= l2->val)
           {
               if(!head)
               {
                   head = tail = new ListNode(l1->val);
                   l1 = l1->next;
               }
               else
               {
                   tail->next = new ListNode(l1->val);
                   tail = tail->next;
                   l1 = l1->next;
               }
           } 
           else
           {
               if(!head)
               {
                   head = tail = new ListNode(l2->val);
                   l2 = l2->next;
               }
               else
               {
                   tail->next = new ListNode(l2->val);
                   tail = tail->next;
                   l2 = l2->next;
               }
           }
       }
       //当某链表已经到达最后一个元素时,证明该链表的最大值也小于另一链表的值,tail直接指向另一链表当前位置
    tail->next = (l1 ? l1:l2) ;
    return head;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

运行结果

在这里插入图片描述

题库24题:两两交换链表中的节点(中等)

题目描述

在这里插入图片描述

思路

在这里插入图片描述

解法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* temp = dummyhead;
        while(temp->next != nullptr && temp->next->next != nullptr)
        {   
            ListNode* n1 = temp->next;
            ListNode* n2 = temp->next->next;
            temp->next = n2;
            n1->next = n2->next;
            n2->next = n1;
            temp = n1;
        }
        return dummyhead->next;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

题库61题:旋转链表(中等)

题目描述

在这里插入图片描述

思路

计算链表长度并找到尾节点
计算出新head位置,指针指向新head的前一个节点
前一个节点作为新的尾节点,指向null,head指向新head

在这里插入图片描述
在这里插入图片描述

解法

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
    	//链表为空或只有一个元素,直接返回
        if(!head || !head->next)
            return head;
        int n = 1;
        ListNode* p = head;
        ListNode* q = head;
        //找到尾节点并计算链表长度
        while(p->next)
        {
             p = p->next;
            n++;
        }
        //计算循环的实际 次数
        k = k%n;
        if(!k)
            return head;
        p->next = head;
        for(int i = 0;i < n - k - 1;i++)
           q = q->next;
        head = q->next;
        q->next = NULL;
        return head;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

运行结果

在这里插入图片描述

题库83题:删除列表中的重复元素(简单)

题目描述

在这里插入图片描述

思路

建立哑节点指向头节点
cur指针不断后移,如果和head指向的节点相同就一直后移,若不同则head和cur均后移

解法

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        if(!head || !head->next)
            return head;
        while(cur)
        {
            if(cur->next && cur->val == cur->next->val)
            {
                while(cur->next && cur->val == cur->next->val)
                    cur = cur->next; 
                cur = cur->next;    
                head->next = cur;
                head = head->next;
            } 
            else if(cur->next && cur->val != cur->next->val)
            {
                cur = cur->next;
                head->next = cur;
                head = head->next;
            }
            else
                return dummyhead->next;
        }
        return dummyhead->next;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

运行结果

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/数据科学创新者/article/detail/62824
推荐阅读
相关标签
  

闽ICP备14008679号