专栏首页C++的沉思链表常见操作总结及C++实现
原创

链表常见操作总结及C++实现

链表

基本技能

  • NULL异常处理
  • dummy node哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点常见题型83. 删除排序链表中的重复元素给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* current = head;
        while (current)
        {
            while (current->next && current->next->val == current->val)
            {
                ListNode* rmNode = current->next;
                current->next = current->next->next;  
                delete rmNode;
            }
            current = current->next;
        }
        return head;
    }
};

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL)
            return head;
        // 链表头也可能删除,所以用dummy node进行辅助
        ListNode dummy(0);
        dummy.next = head;
        head = &dummy;
        while (head->next && head->next->next)
        {
            if (head->next->val == head->next->next->val)
            {
                int rmVal = head->next->val;
                while (head->next && head->next->val == rmVal)
                {
                    ListNode* rmNode = head->next;
                    head->next = head->next->next;
                    delete rmNode;
                }
            }
            else
                head = head->next;
        }
        return dummy.next;
    }
};

206. 反转链表

翻转一个单链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* reverse = NULL;
        ListNode* next;
        while (head)
        {
            next = head->next;
            head->next = reverse;
            reverse = head;
            head = next;
        }
        return reverse;
    }
};

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

class Solution {
public:
    /**
     *        prev   cur
     *          |      |
     *          1  ->  2  ->  3  ->  4  ->  5  ->  NULL  
     *       
     *        prev
     *          |---------------------             cur
     *          |                    |              |
     *          1      4  ->  3  ->  2  ->  NULL    5
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        for (int i = 1; i < m; ++i)
        {
            prev = prev->next;
        }

        ListNode* cur = prev->next;
        ListNode* reverse = NULL;
        for (int i = m; i <= n; ++i)
        {
            ListNode* next = cur->next;
            cur->next = reverse;
            reverse = cur;
            cur = next;
        }

        prev->next->next = cur;
        prev->next = reverse;

        return dummy.next;
    }
};

25. K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (isNeedRevese(prev->next, k))
        {
            ListNode* reverse = NULL;
            ListNode* cur = prev->next;
            for (int i = 0; i < k; ++i)
            {
                ListNode* next = cur->next;
                cur->next = reverse;
                reverse = cur;
                cur = next;
            }

            prev->next->next = cur;
            ListNode* tmp = prev;
            prev = prev->next;
            tmp->next = reverse;
        }

        return dummy.next;
    }
    bool isNeedRevese(ListNode* head, int k)
    {
        ListNode* cur = head;
        int i = 0;
        for (; cur && i < k; ++i)
            cur = cur->next;
        return i == k;
    }
};

21. 合并两个有序链表

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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* p = &dummy;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            } 
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }

        p->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

86. 分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3

输出: 1->2->2->4->3->5

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode smallerDummy(0);  // 小于x的dummy
        ListNode biggerDummy(0);    // 大于x的dummy
        ListNode* smaller = &smallerDummy;
        ListNode* bigger = &biggerDummy;
        while (head) 
        {
            if (head->val < x) {
                smaller->next = head;
                smaller = smaller->next;
            } else {
                bigger->next = head;
                bigger = bigger->next;
            }
            head = head->next;
        }
        
        bigger->next = NULL;
        smaller->next = biggerDummy.next;

        return smallerDummy.next;
    }
};

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序

思路:归并排序,找中点和合并操作

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* mid = middle(head);
        ListNode* tail = sortList(mid->next);
        mid->next = NULL;
        head = sortList(head);
        return mergeList(head, tail);
    }
    ListNode* middle(ListNode* head)
    {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* mergeList(ListNode* l1, ListNode* l2)
    {
        ListNode dummy(0);
        ListNode* p = &dummy;
        while (l1 && l2) 
        {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

143. 重排链表

给定一个单链表 L:L0→L1→…→Ln-1→Ln ,

将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL) 
            return;
        
        ListNode* mid = middle(head);
        ListNode* tail = reverseList(mid->next);
        mid->next = NULL;
        ListNode dummy(0);
        ListNode* p = &dummy;
        bool isHead = true;   //是否取head链表的节点
        while (head && tail) {
            if (isHead) {
                p->next = head;
                head = head->next;
            } else {
                p->next = tail;
                tail = tail->next;
            }
            p = p->next;
            isHead = !isHead;  // 取非,实现间或取值
        }
        p->next = head ? head : tail;

        head = dummy.next;
    }
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* reverse = NULL;
        while (head) {
            ListNode* next = head->next;
            head->next = reverse;
            reverse = head;
            head = next;
        }
        return reverse;
    }
    ListNode* middle(ListNode* head) 
    {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

141. 环形链表

给定一个链表,判断链表中是否有环。

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

142. 环形链表 II

证明:让两个指针其中一个从链表头 head 出发,一次走一步,让另一个指针从相遇点出发,也一次走一步,相遇点就是环的入口。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head; 
        ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next; 
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        
        // 无环
        if (fast == NULL ||fast->next == NULL)
            return NULL;
        
        slow = head;
        while (slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

234. 回文链表

请判断一个链表是否为回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return true;

        ListNode* mid = middle(head);
        ListNode* tail = reverseList(mid->next);
        mid->next = NULL;

        while (head && tail)
        {
            if (head->val != tail->val)
                return false;
            head = head->next;
            tail = tail->next;
        }

        return true;
    }
    ListNode* reverseList(ListNode* head)
    {
        ListNode* reverse = NULL;
        while (head) {
            ListNode* next = head->next;
            head->next = reverse;
            reverse = head;
            head = next;
        }
        return reverse;
    }
    ListNode* middle(ListNode* head)
    {
        // fast如果初始化为head->next则中点在slow->next
        // fast初始化为head,则中点在slow
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        } 
        return slow;
    }
};

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

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。 

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 val, random_index 表示:

val:一个表示 Node.val 的整数。

random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

思路:1、hash 表存储指针,2、复制节点跟在原节点后面

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL)
            return head;

        // 复制节点,紧挨到到后面
        // 1->2->3  ==>  1->1'->2->2'->3->3'
        Node* p = head;
        while (p)
        {
            Node* node = new Node(p->val);
            node->next = p->next;
            p->next = node;
            p = node->next;
        }
        
        // 处理random指针
        p = head;
        while (p)
        {
            if (p->random != NULL)
                p->next->random = p->random->next;
            p = p->next->next;
        }

        // 分离两个链表
        Node dummy(0);
        Node* newList = &dummy;
        p = head;
        while (p)
        {
            newList->next = p->next;
            p->next = p->next->next;
            newList = newList->next;
            p = p->next;
        }

        // 原始链表头:head 1->2->3
        // 克隆的链表头:newList 1'->2'->3'
        return dummy.next;
    }
};

总结

链表必须要掌握的一些点,通过上面的练习题,基本可以应付链表类的各种题目。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++多线程如何获取真正安全的单例

    如果你认为有两种可能,1、2和3、4的话,那说明你是按典型的程序员思维看问题的--没有像编译器和处理器一样处理问题。事实上, 1、4也是一种可能的结果。有两个基...

    evenleo
  • KMP算法分析

    KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫...

    evenleo
  • 二叉树常见算法总结和C++实现

    DFS深度搜索(从上到下)和分治法区别:前者一般将最终结果通过引用参数传入,或者一般递归返回结果最终合并

    evenleo
  • 173. 链表插入排序插入排序

    用插入排序对链表排序 样例 Given 1->3->2->0->null, return 0->1->2->3->null

    和蔼的zhxing
  • 递归:反转链表

    各位小伙伴周末愉快呀~又到了周末咯~我们本周来看看一个反转链表的系列题型吧!整体难度从简单到中等,再到困难,完美符合我们的正常刷题过程。come~

    鹏-程-万-里
  • Day14:链表中倒数第k个结点

    思路一:   我们需要遍历出链表的长度,然后遍历出我们需要的倒数第k个结点,这是我们常规的想法,当然也考虑了代码的鲁棒性和空指针,k为0,k应该大于链表的长度...

    stefan666
  • 【41期】盘点那些必问的数据结构算法题之链表

    来自:juejin.im/post/5b8a0e99f265da43320730ba

    良月柒
  • leetcode链表之删除排序链表中的重复元素

    链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

    codecraft
  • Leetcode链表题目

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    润森
  • leetcode链表之删除排序链表中的重复元素

    链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

    codecraft

扫码关注云+社区

领取腾讯云代金券