【数据结构与算法】手撕链表OJ题

平凡的人1

发布于 2022-11-15 15:27:32

2590

发布于 2022-11-15 15:27:32

文章被收录于专栏：从小白开始修炼

文章目录
移除链表元素
合并两个有序链表
反转链表
链表的中间结点
链表中倒数第k个结点
链表分割
回文链表
相交链表
环形链表
延伸问题
环形链表 II😱
复制带随机指针的链表😰
总结

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

思路一：一种比较普遍的方式，边遍历边找不同。我们可以通过定义两个指针，一个指向头节点，一个置为NULL。当遇到值为相同的时候，直接跳过去。指向下一位。同时，我们要去注意头删的问题，因为题目中给出的函数具有头结点head。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur = head;
    struct ListNode*prev = NULL;
    while(cur)
    {
        if(cur->val == val)
        {
            if(cur==head)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

思路二：给一个新的链表，不是val的结点尾插到新链表即可。最后结点置为NULL。同时，还是要注意头结点的问题

struct ListNode* removeElements(struct ListNode* head, int val){ 
    struct ListNode*cur = head;
    struct ListNode*newhead= NULL,*tail =NULL;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(tail==NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode*del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
    tail->next = NULL;
    return newhead;
}

我们不难发现，如果没有头结点，我们都要去关注，所以我们可以给出带头结点的单链表来进行实现：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur = head;
    struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*tail = guard;
    while(cur)
    {
        if(cur->val != val)
        {
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        else
        {
            struct ListNode*del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
          tail->next = NULL;
    head = guard->next;
    free(guard);
    return head;
}

有头结点之后我们就不需要去考虑删除第一个元素的事了。

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：比较简单，创建一个带头结点的链表，去比较数据的大小尾插到新链表的后面即可。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = NULL;
    struct ListNode*cur1 = list1;
    struct ListNode*cur2 = list2;
    struct ListNode*tail = guard;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next = cur1;
            cur1 = cur1->next; 
        }
        else
        {
            tail->next = cur2;
            cur2 = cur2->next;
        }
        tail = tail->next;
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    struct ListNode*head = guard->next;
    free(guard);
    return head;
}

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路一：取结点头插到新的结点

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

思路二：直接把指针的方向进行翻转即可，使得链表翻转

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur = head;
    struct ListNode*prev = NULL;
    while(cur)
    {
        struct ListNode*next = cur->next;
        cur->next = prev;

        prev = cur;
        cur = next;
    }
    return prev;
}

链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

思路：可以遍历一遍求出长度在除以2。不过我们采用另一种做法只遍历链表一遍即可，采用快慢指针即可。慢指针一次走一步，快指针一次走两步，我们要区分是奇数个结点还是偶数个结点。

对于奇数个：fast到尾，而slow刚好到中间结点

对于偶数个：fast走到空，而slow刚好走到中间结点。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

思路：还是采用快慢指针的做法。slow每次走一步，而fast我们先让它去走K步。然后再同时走。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*slow = pListHead,*fast = pListHead;
    while(k--){
        //k大于链表长度
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

fast如果是先走K-1步呢？既把K–改为–K呢？里面的一些条件我们就需要去进行修改了（我们着重去分析一些边界的问题）：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*slow = pListHead,*fast = pListHead;
    while(fast&&--k){
        fast = fast->next;
    }
      if(fast == NULL)
            return NULL;
    
    while(fast->next){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：我们给出两个带头结点的新链表，值小于X的放在第一条链表，值大于X的放在第二条链表，最后两个新链表连接起来即可。同时，我们需要注意到如果链表为空的时候，我们可以画个图：

public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode*lessguard = (ListNode*)malloc(sizeof(ListNode));
        lessguard->next = NULL;
        ListNode*lesstail = lessguard;
        ListNode*greaterguard = (ListNode*)malloc(sizeof(ListNode));
        greaterguard->next =NULL;
        ListNode*greatertail = greaterguard;
        ListNode*cur = pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
        }
        lesstail->next = greaterguard->next;
        greatertail->next = NULL;
        pHead = lessguard->next;
        free(lessguard);
        free(greaterguard);
        return pHead;
    }
};

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路：找到中间位置，进行后半段逆置，进行比对即可,到最后都为NULL。这其实就是找链表的中间结点以及反转链表的合集：

class Solution {
public:
    //反转链表
      struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* newhead = NULL;
        struct ListNode* cur = head;
        while (cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        return newhead;
    }
    //中间结点
     struct ListNode* middleNode(struct ListNode* head) {
         struct ListNode*slow = head;
         struct ListNode*fast = head;
         while(fast&&fast->next)
         {
             slow = slow->next;
             fast = fast->next->next;
         }
         return slow;

}
    bool isPalindrome(ListNode* head) {
        // write code here
        struct ListNode* mid = middleNode(head);
        struct ListNode* ret = reverseList(mid);
        //1 2 3 2 1
        //先反转中间以后的
        //1 2 1 2 3
        while (head && ret)
        {
            if (head->val == ret->val)
            {
                head = head->next;
                ret = ret->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

另一种解法：创建一个链表使之存放原链表的反转结果，然后在与原链表进行一一对比即可判断是否回文：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // write code here
        struct ListNode*cur = head;
        struct ListNode*newhead = NULL;
        struct ListNode*next = NULL;
        while(cur)
        {
            newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
            newhead->val = cur->val;
            newhead->next = next;
            next = newhead;
            cur = cur->next;
        }
        while(head)
        {
            if(newhead->val!=head->val)
            {
                return false;
            }
            else
            {
                newhead =newhead->next;
                head = head->next;
            }
        }
        return true;
     
    }
};

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

思路：首先需要确定有没有相交，在于尾结点的地址是否相同

找交点——求出长度，既是LenA和LenB的长度。长链表先走差距步，后再同时走，第一个相等就是所求的交点,因为我们已经判断了是否相交。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*curA = headA,*curB = headB;
    int LenA = 0;
    int LenB = 0;
    while(curA)
    {
        curA = curA->next;
        LenA++;
    }
    while(curB)
    {
        curB = curB->next;
        LenB++;
    }
    if(curA!=curB)
    {
        return NULL;
    }
   struct ListNode*longList = headA,*shortList = headB;
   if(LenA<LenB)
   {
       longList = headB;
       shortList = headA;
   }
   int gap = abs(LenA-LenB);
   while(gap--)
   {
       longList = longList->next;
   }
   while(longList != shortList)
   {
       longList = longList->next;
       shortList = shortList->next;
   }
   return longList;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。

思路：带环链表不能遍历。。。我们可以用快慢指针来解决这道题目,快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾：

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

延伸问题

为什么快指针每次走两步，慢指针走一步可以追上，会不会错过？

slow一次走一步，fast一次走三步呢❓
slow一次走一步，fast一次走X步呢❓
slow一次走Y步，fast一次走X步呢❓

后面的问题也是类似的解法，对于slow一次走一步，fast一次走X步呢？每次的距离缩小X-1

而对于slow一次走Y步，fast一次走X步呢？每次的距离缩小X-Y

这其实就是相对距离缩小的问题

环形链表 II😱

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

思路一：这里先说一个结论(入环的第一个节点)：

让一个指针从链表起始位置开始遍历链表，同时让一个指针从相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode*meet = slow;
            while(head!=meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路二：转化成相交链表，从相遇点断开后，作为一个链表，另一个链表从头开始，链表开始入环的第一个节点就相当于这两个链表的交点，而找链表的交点就是上面的题目相交链表。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
 {
     struct ListNode*curA = headA,*curB = headB;
     int LenA = 0,LenB = 0;
     while(curA)
     {
         curA = curA->next;
         LenA++;
     } 
     while(curB)
     {
         curB = curB->next;
         LenB++;
     }
     if(curA != curB)
     {
         retur NULL;
     }
     struct ListNode*longlist = headA,*shortlist = headB;
     if(LenA<LenB)
     {
         longlist = headB;
         shortlist = headA;
     }
     int gap = abs(LenA-LenB);
     while(gap--)
     {
         longlist = longlist->next;
     }
     while(longlist!=shortlist)
     {
         longlist = longlist->next;
         shortlist = shortlist->next;
     }
     return longlist;
 }
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //找到相遇的点
            struct ListNode*meet = slow;
            struct ListNode*next = meet->next;
            //断开
            meet->next = NULL;
           struct ListNode*enterNode = getIntersectionNode(head,next);
           //恢复原来的链表
           meet->next = next;
           return enterNode;
        }
    }
    return NULL;
}

复制带随机指针的链表😰

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码只接受原链表的头节点 head 作为传入参数。

本题较难。如果我们每个节点都去进行复制，这道题的random我们较难去处理：

struct Node* copyRandomList(struct Node* head) {
    //copy节点
	struct Node* cur = head;
    struct Node*copy = NULL;
    struct Node*next = NULL;
    while(cur)
    {
        //赋值链接
        next = cur->next;
        copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        cur->next = copy;
        copy->next = next;
        //迭代
        cur = next;
    }
    
    //更新copy的random
    cur = head;
    while(cur)
    {
        copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        //迭代
        cur = cur->next->next;
    }
    //copy节点解下来链接在一起，恢复原链表
    struct Node*copyHead = NULL,*copyTail = NULL;
    cur = head;
    while(cur)
    {
        copy = cur->next;
        next = copy->next;

        //取节点尾插
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        //恢复原链表
        cur->next = next;

        cur = next;
    }
    return copyHead;
}

总结

通过上面的链表OJ题目，我们对于链表有了更深的了解，同时学会了一些解题的方法，同时，对于做题，我们首先要做的是去理解题目的含义，然后要多去动手画图，方便我们更好地处理一些细节的东西。
当然，链表的OJ题目还有许多，这里的题目只是链表题目的代表而已，并不是说这就是所有链表的题目了，有时间的话，我们还是得多去一些刷题平台做题。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-08-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度