当前位置:   article > 正文

常见链表OJ题_格式化链表

格式化链表

1.移除链表元素

  1. 删除链表中等于给定值 val 的所有节点。(OJ链接)
    在这里插入图片描述
    思想:双指针
  • 首先我们维护一个prev和cur指针,prev先指向NULL,cur用于遍历链表
  • prev用于保存cur的前一个节点,当cur->data等于val,然后自己定义一个next指针保存cur->next,这样就可以先free/delete节点,然后让prev->next指向next,之后把next给到cur就行了
  • 时间复杂度O(n) 空间复杂度0(1)

当头不为空并且第一个节点的data就是val时,直接头节点指向下一个节点
在这里插入图片描述

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //当头不为空并且第一个节点就是val时,直接走到下一个节点
    while(head && head->val == val)  head = head->next;
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
        while(cur)
        {
            if(cur->val == val)
            {
                struct ListNode* next = cur->next;
                prev->next = next;
                free(cur);
                cur = next;
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        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

2.反转链表

  1. 反转一个链表。OJ链接
    在这里插入图片描述思想1:双指针
    时间复杂度O(n) 空间复杂度0(1)

在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

思想2:取节点进行头插
时间复杂度O(n) 空间复杂度0(1)

在这里插入图片描述

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* newnode = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            //取节点进行头插
            cur->next = newnode;
            newnode = cur;
            cur = next;
        }
        return newnode;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3.链表的中间节点

  1. 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个
    中间结点。(OJ链接)
    在这里插入图片描述
    思想:快慢指针->一个指针走一步,另外一个指针走二步
    时间复杂度:0(n) 空间复杂度0(1)

在这里插入图片描述

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        if(head == NULL) return nullptr;
        ListNode* slow = head;
        ListNode* fast = head;
        //快慢指针
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

4.链表中倒数第k个节点

  1. 输入一个链表,输出该链表中倒数第k个结点。(OJ链接)
    在这里插入图片描述思路:定义slow和fast指针,先让slow走k步,然后二个指针一起走,最后走到NULL,fast就是要找的倒数第k个节点
    时间复杂度:0(n) 空间复杂度:0(1)
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        //向让slow走k步
        while(k--)
        {
            //处理k大于链表有效数字情况
            if(slow == NULL) return NULL;
            slow = slow->next;
        }
        //之后slow和fast一起走->slow为空则找到倒数第k个节点
        while(slow != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

5.合并二个有序链表

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

思想:带头单链表
时间复杂度:O(n) 空间复杂度0(1)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode* pHead = new ListNode(-1);
        ListNode* tail = pHead;
        while(list1 && list2)
        {
            if(list1->val < list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 == NULL ? list2 : list1;
        return pHead->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

6.链表分割

编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前。(OJ链接)
在这里插入图片描述

思想:开辟二个带哨兵位的单链表,判断原链表的每个数据,如果小于val则放到第一个链表中,反之放到另外一个链表中,然后将他们链接起来,返回哨兵位的下一个节点

在这里插入图片描述

class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        ListNode* lessHead, *greaterHead, *lesstail, *greatertail;
        lessHead = lesstail = new ListNode(-1);
        greaterHead = greatertail = new ListNode(-1);
        lesstail->next = greatertail->next = NULL;
        ListNode* cur = head;
        while(cur != NULL)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;
                lesstail = cur;
            }
            else
            {
                greatertail->next = cur;
                greatertail = cur;
            }
            cur = cur->next;
        }
        lesstail->next = greaterHead->next;
        greatertail->next = NULL;
        return lessHead->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

7.回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false.(OJ链接)
在这里插入图片描述

思路:找中间节点,反转中间节点之后的节点(包括中间节点),与中间节点之前的节点逐个判断是否相等,相等即为回文,不相等即不是回文。

class Solution {
public:
     //反转链表成员函数
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = NULL;
        ListNode* cur = head;
        while(cur != NULL)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    bool isPalindrome(ListNode* head)
     {
        //首先找链表中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next !=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //逆置(反转)中间节点后面的节点
        slow = reverse(slow);
        //判断是否为回文
        while(head && slow)
        {
            if(head->val == slow->val)
            {
                slow = slow->next;
                head = head->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};
  • 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

8.相交链表

输入两个链表,找出它们的第一个公共结点。(OJ链接)

在这里插入图片描述

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode* tailA = headA,*tailB = headB;
        int lenA = 1, lenB = 1;
        while(tailA->next)
        {
            tailA = tailA->next;
            ++lenA;   
        }
        while(tailB->next)
        {
            tailB = tailB->next;
            ++lenB;
        }
        if(tailA != tailB)
        return NULL;

        //相交,求交点,长的先走差距步,在同时走找交点
        ListNode* shortList = headA,*longList = headB;
        if(lenA > lenB)
        {
            longList = headA;
            shortList = headB;
        }
        int gap = abs( lenA-lenB);
        while(gap--)
        {
            longList = longList->next;
        }
        while(shortList && longList)
        {
            if(shortList == longList)
            return shortList;

            shortList = shortList->next;
            longList = longList->next;
        }
        return NULL;
    }
};
  • 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

9.复制带随机指针的链表

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点,要求返回这个链表的深度拷贝。(OJ链接)

思路:在原链接每一个节点后面链接一个新开辟的节点,节点里面data与原链表节点的data相同,然后"顺藤摸瓜"把原链表的random->next给到新节点的random,最后剪断原链表和新节点之间的链接,让新开辟的节点成为新的链表,并且重新链接原来的链表。
在这里插入图片描述

class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        Node* cur = head;
        while(cur)
        {
            Node* copyNode = new Node(cur->val);
            copyNode->next = cur->next;
            cur->next = copyNode;
            cur = cur->next->next;
        }

        cur = head;
        while(cur)
        {
            if(cur->random == NULL)
            {
            cur->next->random = NULL;
            }
            else 
            {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }

            cur = head;
            Node* copyHead = NULL;
            Node* copytail = NULL;
            while(cur)
            {
                Node* copy = cur->next;
                Node* next = copy->next;
                //原节点重新链接
                cur->next = next;
                if(copyHead == NULL)
                {
                    copyHead = copytail = copy;
                }
                else
                {
                    copytail->next = copy;
                    copytail = copytail->next;
                }
                cur = next;
            }
        return copyHead;
    }
};
  • 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
  • 48
  • 49
  • 50
  • 51
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/689836
推荐阅读
相关标签
  

闽ICP备14008679号