LeetCode 链表(1)

LeetCode 链表(1)

题目

1. 常规题

2 两数相加

给两个链表分别代表两个正数的逆序表示,计算两个链表之和。

依次按位进行相加。

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int acc = 0, val = 0;
        auto head = l1, tail = l1;
        while (l1 && l2) {
            val = l1->val + l2->val + acc;
            acc = val / 10;
            l1->val = val % 10;
            if (!l1->next)
                l1->next = l2->next, l2->next = nullptr;
            tail = l1;
            l1 = l1->next, l2 = l2->next;
        }
        while (l1) {
            val = l1->val + acc;
            acc = val / 10;
            l1->val = val % 10;
            tail = l1;
            l1 = l1->next;
        }
        if (acc)
            tail->next = new ListNode(1);
        return head;
    }
};

21 合并两个有序链表

合并两个有序链表。

逐个比较大小并添加到当前节点后面,并移动对应的链表节点。

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

83 删除排序链表中的重复元素

删除链表中所有重复的节点。

将每个节点与其后面的节点的值做对比,如果相同则删除后面的节点。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto ret = head;
        while (head) {
            while (head->next && head->next->val == head->val) {
                auto next = head->next;
                head->next = next->next;
                delete next;
            }
            head = head->next;
        }
        return ret;
    }
};

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

删除链表中所有重复的节点,只保留原始链表中没有重复出现的数字。

为了删除所有重复的节点并只保留所有没有出现过的数字,需要提前两个节点检查接下来的两个节点的值是否相同,如果相同的话需要将这两个节点及其后的所有重复节点都删除。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *node = new ListNode(0), *ret = node, *next = nullptr, *temp = nullptr;
        node->next = head;
        while (node && node->next) {
            next = node->next->next;
            while (next && node->next->val == next->val) {
                temp = next;
                next = next->next;
                delete temp;
            }
            if (next != node->next->next) {
                temp = node->next;
                node->next = next;
                delete temp;
            } else
                node = node->next;
        }
        return ret->next;
    }
};

203 移除链表元素

删除链表中等于给定值的所有节点。

先判断头节点是否等于给定值,再判断其后面的节点是否等于给定值。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head && head->val == val) {
            auto prev = head;
            head = head->next;
            delete prev;
        }
        auto ret = head;
        while (head) {
            while (head->next && head->next->val == val) {
                auto next = head->next;
                head->next = next->next;
                delete next;
            }
            head = head->next;
        }
        return ret;
    }
};

817 链表组件

给一个链表和一个数组,找到链表中一段子链表的值都在数组中的子链表的个数。

先将数组转换成哈希表方便查询,再依次遍历整个链表,判断一段子链表结束时或遍历结束时子链表是否是符合条件。

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        unordered_set<int> exist(G.begin(), G.end());
        bool cont = false, curr = false;
        int res = 0;
        while (head) {
            curr = exist.count(head->val);
            res += cont && !curr;
            cont = curr;
            head = head->next;
        }
        return res + cont;
    }
};

24 两两交换链表中的节点

给一个链表,返回两两交换其中相邻的节点后的结果。

用三个指针把要交换的两个节点和他们的前驱节点保存下来,交换后再更新三个指针,按顺序交换即可。

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *root = new ListNode(0), *prev = root;
        root->next = head;
        auto first = head, second = head->next;
        while (first && second) {
            auto temp = second->next;
            prev->next = second;
            second->next = first;
            first->next = temp;
            prev = first;
            first = temp;
            second = temp ? temp->next : nullptr;
        }
        return root->next;
    }
};

430 扁平化多级双向链表

给一个带子节点的双向链表,将其扁平化并使所有结点出现在单级双链表中。

对于某一个节点,如果它有 child 节点,那么需要将其 child 节点作为其新的 next 节点,将其 child 链表上的最后一个节点作为其原本 next 节点的 prev 节点,递归调用整个过程即可。

class Solution {
public:
    Node *flatten(Node *head) {
        if (!head)
            return nullptr;
        Node *node = head, *next = nullptr;
        while (node) {
            if (node->child) {
                next = node->next;
                auto child = flatten(node->child);
                node->next = child;
                child->prev = node;
                node->child = nullptr;
                while (node->next)
                    node = node->next;
                node->next = next;
                if (next)
                    next->prev = node;
            }
            node = node->next;
        }
        return head;
    }
};

2. 链表反转

206 反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *prev = nullptr, *curr = head, *next = head->next;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

92 反转链表 II

将链表中从 m 到 n 位置的节点反转。

先找到位置在 m - 1 的节点,将其后的节点截断,再找到位置在 n 的节点,将其后的节点截断,将中间的一段链表反转后再链接到愿链表上。

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *root = new ListNode(0), *r = root, *prev, *last;
        root->next = head;
        int cnt = 1;
        while (cnt < m && r)
            r = r->next, ++cnt;
        prev = r;
        while (cnt <= n && r && r->next)
            r = r->next, ++cnt;
        last = r->next;
        r->next = nullptr;
        prev->next = Reverse(prev->next);
        while (prev && prev->next)
            prev = prev->next;
        prev->next = last;
        return root->next;
    }

    ListNode *Reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

369 给单链表加一

用一个单链表表示一个整数,计算将其加一的结果。

先将链表反转方便进位,然后进行加一和进位的操作,最后再反转一次链表。

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if (!head)
            return nullptr;
        head = Reverse(head);
        auto root = head;
        while (head) {
            if (head->val == 9) {
                head->val = 0;
                if (!head->next) {
                    head->next = new ListNode(1);
                    break;
                }
                head = head->next;
            }
            else {
                ++head->val;
                break;
            }
        }
        return Reverse(root);
    }
    
    ListNode *Reverse(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *prev = nullptr, *curr = head, *next = head->next;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

445 两数相加 II

给两个链表分别代表两个正数,计算两个链表之和。

先将两个链表反转,再依次按位进行相加,最后再将得到的结果反转并返回。

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (!l1 || !l2)
            return !l1 ? l2 : l1;
        l1 = Reverse(l1);
        l2 = Reverse(l2);
        int carry = 0, sum = 0;
        ListNode *head = l1, *prev = l1;
        while (l1 && l2) {
            prev = l1;
            sum = l1->val + l2->val + carry;
            carry = sum / 10;
            l1->val = sum - carry * 10;
            if (l2->next && !l1->next)
                l1->next = l2->next, l2->next = nullptr;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1) {
            prev = l1;
            sum = l1->val + carry;
            carry = sum / 10;
            l1->val = sum - carry * 10;
            l1 = l1->next;
        }
        if (carry && prev)
            prev->next = new ListNode(1);
        return Reverse(head);
    }

    ListNode *Reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

25 K 个一组翻转链表

给一个链表,每 k 个节点一组进行翻转。

用几个指针记录下需要反转的部分的起始,终止位置,依次反转即可。

class Solution {
    ListNode *ReverseLinkedList(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode *root = new ListNode(0), *prev = root;
        prev->next = head;
        while (prev) {
            int i = 1;
            ListNode *start = prev->next, *end = prev->next, *curr = end, *next = nullptr;
            while (curr && i < k)
                curr = curr->next, ++i;
            if (i < k || !curr)
                break;
            next = curr->next;
            curr->next = nullptr;
            start = ReverseLinkedList(start);
            prev->next = start;
            end->next = next;
            prev = end;
        }
        return root->next;
    }
};

3. 双链表

328 奇偶链表

把一个链表中的奇数位节点和偶数位节点分别排在一起。

用两个头节点分别表示奇数位和偶数位节点的起始位置,遍历整个链表,将奇数位节点链接在奇数位起始节点后,将偶数位节点链接在偶数位起始节点后,最后将偶数位起始节点链接在奇数位最后节点后即可。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next)
            return head;
        auto odd = head, even = head->next, node = even->next, even_head = even;
        bool flag = true;
        while (node) {
            if (flag) {
                odd->next = node;
                odd = odd->next;
                flag = false;
            } else {
                even->next = node;
                even = even->next;
                flag = true;
            }
            node = node->next;
        }
        odd->next = even_head;
        even->next = nullptr;
        return head;
    }
};

86 分隔链表

给一个链表和一个值 x,重新排列链表使得所有小于 x 的节点都在大于等于 x 的节点之前。

用两个头节点 sth 和 geq 分别表示小于 x 和大于等于 x 的节点的起始位置,遍历整个链表,分别将各个节点链接到两个头节点之后,最后将 geq 链接到 sth 之后,再将 geq 的末端设为空指针。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        auto sth = new ListNode(0), sth_head = sth, geq = new ListNode(0), geq_head = geq;
        while (head) {
            if (head->val < x) {
                sth->next = head;
                sth = sth->next;
            } else {
                geq->next = head;
                geq = geq->next;
            }
            head = head->next;
        }
        sth->next = geq_head->next;
        geq->next = nullptr;
        return sth_head->next;
    }
};

725 分隔链表

给一个链表, 将其分隔为 k 个连续的部分。

先计算出链表的长度和 k 个连续部分中每个部分的长度,依次将每个部分的头节点放入数组中。

class Solution {
public:
    vector<ListNode *> splitListToParts(ListNode *root, int k) {
        vector<ListNode *> res(k, nullptr);
        int len = 0;
        ListNode *head = root, *temp = nullptr;
        while (root)
            root = root->next, ++len;
        int n = len / k, m = len % k, i = 0;
        while (head) {
            res[i] = head;
            for (int j = 0; j < n + (m > 0) - 1; ++j)
                head = head->next;
            temp = head;
            head = head->next;
            temp->next = nullptr;
            ++i;
            --m;
        }
        return res;
    }
};
comments powered by Disqus