链表练习题-1

简介: 链表练习题

移除链表元素

移除链表元素

a2c68a399d61b77d548f809b2f3a9f0a_2179838da4944769a9d76328719ae00e.png

这道题有多种思路,双指针法

思路:遍历一遍,在中途中我们要找出要删除的节点,并把要删除的节点进行free,我们要注意的就是

9731e832f1840d3136e50d30b3d8b3ff_af1d17efcb5046cea5fe8b5a4b61fff0.png

我们通过判断tail->val是否为要删除的值,如果不是就prev = tail, tail = tail->next,如果是的话,我们就要删除, 然后tail存储下一个节点的地址,而prev不变,

我们要考虑一些情况,当我们删除的是第一个节点,那head存储的地址就要改变,

循环结束的条件就是

52de492d9febef1e960eb82f8e4fb2be_f49f75e4afbd4c669f89c716fe59316a.png


tail的值为NULL,就是循环停止的时候


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    //遍历一遍
    while (cur)
    {
        if (cur->val == val)
        {
            struct ListNode* nex = cur->next;
            if (prev)
            {
                prev->next = nex;
            }
            //判断是否要删除第一个节点
            else
            {
                head = nex;
            }

            free(cur);
            cur = nex;

        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

二指针加空链表法(尾插思路)


1e94c2338302f49ea9e4695b4b41e73c_35cc7f8927ed44a593646b252ebe7be0.png

cur去判断该节点是否符合,引用新的newhead指向符合条件的节点,符合就添加到newhead,不是就free,然后cur指向下一个节点,tail不动,有两种特殊情况,一种的head=NULL,一种是free最后一个节点,前一个节点的next没有NULL


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* newnode = NULL;
    struct ListNode* cur = head;
    struct ListNode* tail = NULL;
    while (cur)
    {
        if (cur->val != val)
        {
            if (tail == NULL)
            {
                newnode = cur;
                tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = cur;
                
            }
            cur = cur->next;
        }
        else
        {
            //保存下一个节点
            struct ListNode* p = cur->next;
            free(cur);
            cur = p;
        }
    }
    //假设head为NULL
    if (tail)
        tail->next = NULL;
    return newnode;
 }

哨兵位方法

b2194e15714cd1a53c24a8306ffb8750_99ccd536648344ac86c4584d269d371a.png

这里的头节点不是d1而是head也称哨兵位头节点

这个带哨兵位的链表的好处就是头节点一定存在,地址不为空,


d1195b8c7d1346b60f7d1b49ff02e55f_41de10e3d5b14082861100f40d8b08f4.png

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //创建哨兵位
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head;
    struct ListNode* tail = newnode;
    while (cur)
    {
        if (cur->val != val)
        {
           tail->next = cur;
           cur = cur->next;
           tail = tail->next;
        }
        else
        {
            //保存下一个节点
            struct ListNode* p = cur->next;
            free(cur);
            cur = p;
        }
    }
    //假设head为NULL
    tail->next = NULL;
    //释放哨兵
    struct ListNode*p = newnode->next;
    free(newnode);
    return p;
  }

分割链表

分割链表

c028c824608437258e45347ec14e1342_a63635e135db47efa3031c5c9c4da891.png

方法1:创建两个空链表 链表1存储小于X的所有节点,链表2存储大于等于x的所有节点,然后两个链表链接起来,

3f2bd77187bc4fb71e48bf3ae0eb4acf_f4fd0f7e68c64da4b9e548a6aa730b30.png

 ListNode* partition(ListNode* pHead, int x) 
    {
        //小
        struct ListNode *head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *tail1 = head1;
        //大
        struct ListNode *head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *tail2 = head2;
        struct ListNode *cur = pHead;
        while (cur) 
        {
            if(cur->val < x)
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
            else
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
            cur = cur->next;
        
        }
        //防止head2最后一个节点的next不为NULL
        tail2->next = NULL;
        tail1->next = head2->next;
        struct ListNode *ph = head1->next;
        free(head1);
        free(head2);
        return ph;

       
    }

我们需要注意的是head2的最后一个节点的next可能指向野指针,也可能形成环状链表,


反向链表

反向链表

6e086763a87496d5932dec20f531f156_635c4ad08e594ad2be419df726c64958.png

方法1

三指针反转

d1eb3925010b6a1f1f50ffe26ff2bd58_db81a5cf1e1846a7bd7e7360235a46ad.png

主要进行交换的是n1和n2这两个指针,n3指针是辅助n2能找到下一个节点的地址

循环结束就是

609241121108ea7ed3fb348d12515a3c_13dd136a5c384c368899f2ef86d2f217.png

当n2 = NULL或者是n1->next = NULL循环结束

struct ListNode* reverseList(struct ListNode* head) 
{
    if (head == NULL)
        return head;
    struct ListNode *n1 = NULL;
    struct ListNode *n2 = head;
    struct ListNode *n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    return n1;
}

方法二:创建空链表,头插

9a6426fe84da9da8ce0469f5f0a3a377_b850f0bd9694459592ca7e631926dca1.png

思路:把旧链表的节点取下来,然后头插到新链表中

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* newnode = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
         struct ListNode* pn = cur->next;
        cur->next = newnode;
        newnode = cur;
        cur = pn;
    }
    return newnode;
}

链表中倒数第k个结点

链表中倒数第k个结点

3862aca27f9d9666f7fb61d1840a6576_68587446b62e4ddaac2d36e3670418bc.png

方法1暴力法

先求出链表的长度,然后长度减去倒数的个数,再遍历一遍


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* tail = pListHead;
    if (tail) {
        int size = 1;
        while (tail->next) {
            tail = tail->next;
            size++;

        }
        tail = pListHead;
        if (k > size) {
            return NULL;
        }
        while (size > k) {
            tail = tail->next;
            size--;
        }

        return tail;
    }
    else {
    return NULL;
    }
}

时间复杂度是O(n)

但是不够高效


方法二

双指针距离差

创建两个指针,指向头节点,然后一个一个节点也走k步,然后两个指针一起走,当走k步的那个指针为NULL就结束

结束标记

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead, *slow = pListHead;
    //fast先走k步
    while(k--)
    {
        //防止为空
        if(fast ==NULL)
            return NULL;
        fast = fast->next;
    }
    //一起走
    while (fast) 
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}


链表练习题-2

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

相关文章
|
7月前
|
算法 索引
链表经典练习题
链表经典练习题
|
7月前
|
安全
链表练习题-2
链表练习题
|
7月前
【链表之练习题】
【链表之练习题】
47 1
|
7月前
【无头双向链表和链表练习题2】
【无头双向链表和链表练习题2】
38 0
|
存储 算法
做几个链表相关的练习题吧!!
做几个链表相关的练习题吧!!
56 1
|
7月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
58 2
|
7月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1