链表练习题-2

简介: 链表练习题

链表练习题-1

https://developer.aliyun.com/article/1498105


相交链表

相交链表

526196e7f66c6ddd5c98f0ebe895b8bf_5db9f53c306a421daf0dd1a587265030.png

方法1:暴力法

A中的每个节点的地址在B链表都找一遍,然后比较,时间复杂度是O(n^2)


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
 {
     struct ListNode* taila = headA;
     
     while(taila)
     {
         struct ListNode* tailb = headB;
         while(tailb)
         {
             if(taila == tailb)
             {
                 return tailb;
             }
             tailb = tailb->next;
         }
         taila = taila->next;
     }
    return NULL;
}

方法2

两个链表遍历一遍,然后找出尾节点进行比较地址,相同则继续计算长度,长度大的先走,走到剩下的长度和另外一个链表的长度一样,然后一起走,然后一一比较节点的地址

97a6ff393c4cdc8ea33934373450f5d2_f78c1360aeff42609e291cd1f774416d.png

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
 {
     if(!(headA && headB))
        return NULL;
    struct ListNode* tail1 = headA;
    struct ListNode* tail2 = headB;
    int conut1 =1;
    int conut2 =1;
    //找出尾节点,随便算出cah
    while(tail1->next)
    {
        tail1 = tail1->next;
        conut1++;
    }
    while(tail2->next)
    {
        tail2 = tail2->next;
        conut2++;
    }
    if(!(tail1 == tail2))
        return NULL;
    struct ListNode* maxh = (conut1 >= conut2 ? headA : headB);
     struct ListNode* minh = (conut1 >= conut2 ? headB : headA);
    int i = 0;
    for (i = 0; i <abs(conut1 -conut2);i++)
    {
        maxh = maxh->next;
    }
    while(minh)
    {
        if(maxh == minh)
        {
            return maxh;
        }
        maxh = maxh->next;
        minh = minh->next;
    }
    return NULL;
}

环形链表

环形链表

f1c0141536639bc86a72bfab6cf5b5c8_cec19671a6b54a46a723e6e23bb46a77.png

这里考察带环链表

代环链表:尾节点的next指向链表的任意节点

看到这里可能会想到遍历一遍,找出尾节点,这样很容易陷入死循环,或者有人想到找节点比较,怎么找,因为节点是不确定的,无法这样

这个题可以使用漏洞法

bool hasCycle(struct ListNode *head) 
{
    struct ListNode*tail = head;
    int a = 10002;
    while(tail)
    {
        if(a==0)
            return true;
        a--;
        tail = tail->next;

    }
    return false;
}

222b4dba0c451c0ac87f5236865957c3_d9af824030e144d5aaf1874ccc1e0aba.png

可以判断如果循环次数超出节点数就可以判断是有环的,否则就是无环的这种方法不推荐

方法2:快慢指针速度差法

slow一次走一步,fast一次走两步,当slow刚刚进入到环里面时

fast和slow的距离就是X,转换成fast追逐slow

v1 t - v2t = X, t = x/(v1 - v2)


bool hasCycle(struct ListNode *head) 
{
    struct ListNode* slow = head, *fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}

环形链表 II

环形链表 II

e9bdb4fe12d252825709fc81229b482b_b9c13d37a08245b18aa81b2481cc335b.png

思路:

快慢指针求出相遇点



slow一次走一步,fast一次走两步,当slow刚刚进入到环里面时,fast和slow的距离就是X,转换成slow和fast在入环点的经过x的长度相遇,c为环的长度

写成 2(L+x) = n*c + L +x

化简成L = (n-1)*c + c - x

image.png

所以我们求出入环点可以这样,一个指针在fast和slow相遇的节点开始循环,一个指针从头节点开始走,最终一定会在入环点相遇


struct ListNode *detectCycle(struct ListNode *head) 
{
    if(head == NULL)
        return NULL;
    struct ListNode*tail = head;
    struct ListNode*prev = head;
    //找出相遇点
    while (prev && prev->next)
    {
       
        tail = tail->next;
        prev = prev->next ->next;
        //找出相遇点
        if(tail == prev)
        { //开始两个指针走
            tail = head;
            while(tail != prev)
            {
                tail = tail->next;
                prev = prev->next;
            }
            return tail;
        }
    }

    return NULL;  
}

转换相交链表解决

先找出相遇点,然后一个指针指向相遇点的下一个节点,把相遇点的next =NULL,然后一个指针从head开始走,变成找两链表找交点


 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
 {
     if(!(headA && headB))
        return NULL;
    struct ListNode* tail1 = headA;
    struct ListNode* tail2 = headB;
    int conut1 =1;
    int conut2 =1;
    //找出尾节点,随便算出cah
    while(tail1->next)
    {
        tail1 = tail1->next;
        conut1++;
    }
    while(tail2->next)
    {
        tail2 = tail2->next;
        conut2++;
    }
    if(!(tail1 == tail2))
        return NULL;
    struct ListNode* maxh = (conut1 >= conut2 ? headA : headB);
     struct ListNode* minh = (conut1 >= conut2 ? headB : headA);
    int i = 0;
    for (i = 0; i <abs(conut1 -conut2);i++)
    {
        maxh = maxh->next;
    }
    while(minh)
    {
        if(maxh == minh)
        {
            return maxh;
        }
        maxh = maxh->next;
        minh = minh->next;
    }
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    if(head == NULL)
        return NULL;
    struct ListNode*tail = head;
    struct ListNode*prev = head;
    //找出相遇点
    while (prev && prev->next)
    {
       
        tail = tail->next;
        prev = prev->next ->next;
        //找出相遇点
        if(tail == prev)
        { //开始两个指针走
            tail = head;
            struct ListNode*p = prev->next;
            prev->next = NULL;
            p = getIntersectionNode(tail, p);
            if(p)
                return p;
        }
    }

    return NULL;  
}

合并两个有序链表

合并两个有序链表

df863021b8e8f08fd9d0558b9fdbbb58_572d65f682f94f93a8f0ef7bc4cb1171.png

思路:这里的思路和顺序表的(两顺序表合成一个顺序表)很像,创建两个指针分别指向l1和l2的头节点,创建一个空链表和一个指针,l1和l2的链表的节点进行判断,然后放入到空链表中,然后把剩下的节点一并插入到链表中

这里的空链表可以是带哨兵位的也可以不要

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode*newnode =NULL;
    struct ListNode*prev =NULL;
    struct ListNode* tail1 = list1;
    struct ListNode* tail2 = list2;
    while(tail1 && tail2)
    {
        if(tail1->val < tail2->val)
        {
            if(prev == NULL)
            {
                newnode = tail1;
                prev = tail1;
                tail1 = tail1->next;
            }
            else
            {
                prev->next = tail1;
                prev = prev->next;
                tail1 = tail1->next;
            }
        }
        else
        {
            if(prev == NULL)
            {
                newnode = tail2;
                prev = tail2;
                tail2 = tail2->next;
            }
            else
            {
                prev->next = tail2;
                prev = prev->next;
                tail2 = tail2->next;
            }
        }
    } 
    if(tail1)
        prev->next = tail1;
    if(tail2)
        prev->next = tail2;
    return newnode;








    // if(list1 == NULL)
    //     return list2;
    // if(list2 == NULL)
    //     return list1;
    // //哨兵位
    // struct ListNode *newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    // struct ListNode* tail1 = list1;
    // struct ListNode* tail2 = list2;
    // struct ListNode* prev = newnode;
    // while(tail1 && tail2)
    // {
    //     if(tail1->val > tail2->val)
    //     {
    //         prev->next = tail2;
    //         tail2 = tail2->next;
    //     }
    //     else
    //     {
    //         prev->next = tail1;
    //         tail1 = tail1->next;
    //     }
    //     prev = prev->next;
    // }
    // if(tail1)
    //     prev->next = tail1;
    // if(tail2)
    //     prev->next = tail2;
    // struct ListNode *ph = newnode->next;
    // free(newnode);
    // return ph;
}

链表的回文结构

链表的回文结构


9b99311cdb90cc79db81a8f2030a3463_f3b8c17b405c435d9fc05e6f3ef2a8d4.png

思路:我们可以先找到这个链表的中间节点,然后把后半段的链表逆置过来,然后转换成两个链表(节点数一样的)对应的节点一一比较


a4b3bd26795fa017c729c26483833e7b_13822910fd1b411b93e84be772fe37fb.png

class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) 
    {
         if(head == NULL)
            return true;
        //双指针速度差法
       
        struct ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            fast = fast ->next ->next;
            slow = slow->next;
        }
        //slow为中间节点
        //后部分反转
    
    struct ListNode *n1 = NULL;
    struct ListNode *n2 = slow;
    struct ListNode *n3 = slow->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
   
        //fast为第二个链表头节点地址
        fast = n1;
        slow = head;
        while(slow && fast)
        {
            if(slow->val != fast->val)
            {
                return false;
            }
            slow = slow->next;
            fast = fast->next;
            
        }
        return true;
        
        //双指针比较
    }
};

随机链表的复制

随机链表的复制

15d5b2c41c9ca908fa21ff5b41dc1f27_2e933028b0d544f4a9b8919e3af91c51.png

思路:

5685cfef3dbeb7d145c9a0912103b522_9497d88236d644f4a9b4a502ea09b4fe.png

我们可以像上图一样,往每个原节点的后面插入一个和该节点相同值的节点,然后我们在原节点的找到random, 每个原节点的后一个节点就是复制的节点,我们可以通过这种特性把复制的节点的random进行连接,然后创建一个空链表,把复制的节点进行连接,


struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL)
        return NULL;
    struct Node *cur = head;
    while(cur)
    {
        //创建节点
        struct Node *copy = (struct Node *)malloc(sizeof(struct Node));
        copy->val = cur->val;
        struct Node *cp = cur->next;
        cur->next = copy;
        copy->next = cp;
        cur = cp;
    }
    //开始指向random
    cur = head;
   
    while(cur)
    {
         struct Node *cp = cur->next;
        if(cur->random)
            cp->random = cur->random->next;
        else
            cp->random = NULL;
        cur = cur->next->next;
        

    }
    //创建空链表,然后尾插
    //创建哨兵位
    struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
     struct Node *tail = newnode;
    //开始尾插
    cur = head;
    while(cur)
    {
        struct Node *new = cur->next;
        tail->next = new;
        tail = tail->next;
        cur = new->next;
    }
   
    struct Node *p = newnode->next;
    free(newnode);
    return p;
}
相关文章
|
18天前
|
算法 索引
链表经典练习题
链表经典练习题
17 0
|
30天前
|
存储
链表练习题-1
链表练习题
|
30天前
【无头双向链表和链表练习题2】
【无头双向链表和链表练习题2】
26 0
|
30天前
【链表之练习题】
【链表之练习题】
28 1
|
8月前
|
存储 算法
做几个链表相关的练习题吧!!
做几个链表相关的练习题吧!!
31 1
|
30天前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
4天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
4天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】