LeetCode 链表(1)

Alex_Shen
2021-02-13 / 0 评论 / 0 点赞 / 76 阅读 / 4,586 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Leetcode 题解 - 链表

链表是空节点,或者有一个值和一个指向下一个链表的指针,因此很多链表问题可以用递归来处理。

160. 找出两个链表的交点

160. Intersection of Two Linked Lists (Easy)

Leetcode / 力扣

思路是利用双指针遍历A+B链表,直到遇到同一个结点。

当访问 A 链表的指针访问到链表尾部时,令它从链表 B 的头部开始访问链表 B;同样地,当访问 B 链表的指针访问到链表尾部时,令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点(原因:访问长度均为——A独立部分+共同部分+B独立部分)

如果不存在交点,那么 a + b = b + a,以下实现代码中 p1 和 p2 会同时为 null,从而退出循环。

时间复杂度O(m+n),空间复杂度O(1)

	ListNode *reverseList(ListNode *head)
    {
        ListNode *pre = nullptr, *next = head;
        while (next)
        {
            auto temp = next->next;
            next->next = pre;
            pre = next;
            next = temp;
        }
        return pre;
    }

如果只是判断是否存在交点,那么就是另一个问题,即 编程之美 3.6 的问题。有两种解法:

  • 把第一个链表的结尾连接到第二个链表的开头,看第二个链表是否存在环;
  • 或者直接比较两个链表的最后一个节点是否相同。

206. 链表反转

206. Reverse Linked List (Easy)

Leetcode / 力扣

递归

思路:递归将链表指向反转

    ListNode *reverseList(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode* next = head->next;
        ListNode* newHead = reverseList(next);
        next->next = head;
        head->next = NULL;
        return newHead;
    }

双指针法

思路:利用两个指针记录前后两个结点,将后一个结点指向前一个结点,并且借用temp指针将两个指针向后移动一位。

注:pre一开始设为NULL(新链表的尾)。最后next为NULL、pre为最后一个结点,所以返回pre指针。

时间复杂度O(n),空间复杂度O(1)。

    ListNode *reverseList(ListNode *head)
    {
        ListNode *pre = nullptr, *next = head;
        while (next)
        {
            auto temp = next->next;
            next->next = pre;
            pre = next;
            next = temp;
        }
        return pre;
    }

21. 归并两个有序的链表

21. Merge Two Sorted Lists (Easy)

Leetcode / 力扣

思路:创建新的链表,比较l1与l2的元素值大小,将小的插入新的链表之中。当l1或l2结束后,将剩余元素全部插入新链表之中。

时间复杂度O(m+n),空间复杂度O(m+n)。

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *ans, *p;
        ans = new ListNode(0);
        p = ans;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p->next = new ListNode(l1->val);
                p = p->next;
                l1=l1->next;
            }
            else
            {
                p->next = new ListNode(l2->val);
                p = p->next;
                l2=l2->next;
            }
        }
        p->next = (l1 == NULL) ? l2 : l1;
        return ans->next;
    }

83. 从有序链表中删除重复节点

83. Remove Duplicates from Sorted List (Easy)

Leetcode / 力扣

思路:遍历链表,如果当前结点与下一节点相同则删除下一个结点。

    ListNode *deleteDuplicates(ListNode *head)
    {
        ListNode *p = head;
        while (p&&p->next)
        {
            ListNode *next=p->next;
            if(next->val==p->val){
                p->next=p->next->next;
                delete next;
                continue;
            }
            p=p->next;
        }
        return head;
    }

19. 删除链表的倒数第 n 个节点

19. Remove Nth Node From End of List (Medium)

Leetcode / 力扣

思路:快慢指针,先让快指针向前n步,然后同时前进。当快指针到尾部时,慢指针指向倒数第n个节点。注意当删除第一个节点时要特殊考虑

    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *fast = head, *slow = head;
        while (n--)
            fast = fast->next;
        if (fast == NULL)
            return head->next;
        while (fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }

24. 交换链表中的相邻结点

24. Swap Nodes in Pairs (Medium)

Leetcode / 力扣

思路:记录连续三个结点,首先交换first与second结点,然后将pre指向second(此时已经交换完成了)

    ListNode *swapPairs(ListNode *head)
    {
        ListNode *ans = new ListNode(-1);
        ans->next=head;
        ListNode *pre = ans;
        while (pre->next && pre->next->next)
        {
            ListNode *first=pre->next,*second=pre->next->next;
            first->next = second->next;
            second->next = first;
            pre->next = second;
            pre = first;
        }
        return ans->next;
    }

445. 链表求和

445. Add Two Numbers II (Medium)

Leetcode / 力扣

思路:数字求和符合正常计算顺序是由地位到高位,所以选择用栈结构。
首先将数字读入两个栈之中,然后利用相加整除/求余获得对应数字及进位。
注意:while中cur!=0是为了排除相同位数数字相加且最高位进位的情况(如5+5=10)

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        stack<int> s1, s2;
        while (l1)
        {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2)
        {
            s2.push(l2->val);
            l2 = l2->next;
        }
        ListNode *ans = NULL;
        int carry = 0;
        while (!s1.empty() || !s2.empty() || carry != 0)
        {
            int a = s1.empty() ? 0 : s1.top();
            if (!s1.empty())
                s1.pop();
            int b = s2.empty() ? 0 : s2.top();
            if (!s2.empty())
                s2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur = cur % 10;
            ListNode *head = new ListNode(cur);
            head->next = ans;
            ans = head;
        }
        return ans;
    }

234. 回文链表

234. Palindrome Linked List (Easy)

Leetcode / 力扣

思路:先计算链表元素总数cnt,然后将前半部分元素存入栈中,后半元素与栈顶元素一一比对。如果是奇数链表则跳过中间元素。
时间复杂度O(2n),空间复杂度O(n)。
注:题目要求时间复杂度O(n),空间复杂度O(1),后续在更新更简单的算法。

    bool isPalindrome(ListNode *head)
    {
        int cnt = 0;
        ListNode *current = head;
        while (head)
        {
            cnt++;
            head = head->next;
        }
        stack<int> s;
        bool ans = true;
        for (int i = 1; i <= cnt; i++)
        {
            if (i <= cnt / 2)
                s.push(current->val);
            if (i == cnt / 2 + 1 && cnt % 2 == 1){
                current = current->next;
                continue;
            }
            if (i > cnt / 2)
            {
                if (s.top() != current->val)
                {
                    ans = false;
                    break;
                }
                s.pop();
            }
            current=current->next;
        }
        return ans;
    }

725. 分隔链表

725. Split Linked List in Parts(Medium)

Leetcode / 力扣

思路:第一次遍历链表计算元素总数。计算可得,前“余数”组的元素个数为“商+1”,后“余数”组的元素个数为“商”。
第二次遍历根据计算结果进行分组,将头节点传入数组,并将尾结点指向空指针。

    vector<ListNode *> splitListToParts(ListNode *root, int k)
    {
        ListNode *temp = root;
        vector<ListNode *> ans;
        int num = 0;
        while (temp)
        {
            num++;
            temp = temp->next;
        }
        int quotient = num / k, remainder = num - quotient * k;
        while (k--)
        {
            if (root)
            {
                ans.push_back(root);
                int cnt = remainder > 0 ? quotient + 1: quotient;
                remainder--;
                while (cnt--){
                    if(cnt==0){
                        ListNode *temp = root;
                        root = root->next;
                        temp->next = NULL;
                    }
                    else
                        root = root->next;
                }
            }
            else
                ans.push_back(NULL);
        }
        return ans;
    }

10. 链表元素按奇偶聚集

328. Odd Even Linked List (Medium)

Leetcode / 力扣

原项目地址:https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E9%93%BE%E8%A1%A8.md

0

评论区