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

原创

evenleo

修改于 2020-09-24 17:11:54

4790

修改于 2020-09-24 17:11:54

文章被收录于专栏：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;
    }
};

总结

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

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

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

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

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

编程算法

登录后参与评论

0 条评论

热度