专栏首页算法工程师之路链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

1

编程题

【LeetCode #147】对链表进行插入排序

对链表进行插入排序。

示例 1: 输入: 4->2->1->3 输出: 1->2->3->4

解题思路:

首先判断两个相邻节点的大小,如果head->val > head->next->val,则需要将head->next->val插入到从dummy节点开始遍历第一个大于head->next->val节点的前面!好好理解这句话!在进行插入的时候,首先使用cur指针标记head->next节点,并改变head->next的指向。从而将待插入节点分离!接着就是普通的插入操作了!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* dummy = new ListNode(), *pre = nullptr;
        dummy->next = head;
        while(head->next != nullptr){
            if(head->val <= head->next->val){  // 无需进行插入操作
                head = head->next;
                continue;
            }
            pre = dummy;
            while(pre->next->val < head->next->val){
                pre = pre->next;
            }
            ListNode* cur = head->next;
            head->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
        }
        return dummy->next;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/insertion-sort-list/

【LeetCode #876】链表的中间结点

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

示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。(测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

解题思路:快慢指针,注意与下一题中的回文链表的中间结点进行区别!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/middle-of-the-linked-list

【LeetCode #234】回文链表

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

示例 1: 输入: 1->2 输出: false

解题思路:

找到中点(奇数时不是真正的中点,注意与上题区别),然后反转后面的链表,再进行节点值得比较即可!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head, *fast = head, *pre = nullptr;
        while(fast != nullptr){
            slow = slow->next;
            fast = fast->next ? fast->next->next : nullptr;
        }   // 这里的中点偶数时为第二个节点,奇数时为中点的下一个节点!
        while(slow != nullptr){
            ListNode* next = slow->next;
            slow->next = pre;
            pre = slow;
            slow = next;
        }
        while(pre && head){
            if(pre->val != head->val){
                return false;
            }
            pre = pre->next;
            head = head->next;
        }
        return true;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/middle-of-the-linked-list

【LeetCode #817】链表组件

给定一个链表(链表结点包含一个整型值)的头结点 head。 同时给定列表 G,该列表是上述链表中整型值的一个子集。 返回列表 G 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 G 中)构成的集合。

示例 1: 输入: head: 0->1->2->3 G = [0, 1, 3] 输出: 2 解释: 链表中,0 和 1 是相连接的,且 G 中不包含 2,所以 [0, 1] 是 G 的一个组件,同理 [3] 也是一个组件,故返回 2。

解题思路:

一开始题目没有看太懂,可能语文不太好!他的意思就是,如果连续相邻的链表节点值都在G这个数组中,那么这为一个组件,如果不在,则忽略!最终答案是G中有多少个组件。 比如0->1->3->2, 而G = [1,3,0] 则答案为 1。 我们查询可以在set中进行,设置布尔变量flag的作用是:用true标记这是一个组件,而false表示组件断开了,此时res++, 但有可能我们遍历的节点一直都不在G中。因此res++需要一个条件限制,即flag = true.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        set<int> s(G.begin(), G.end());
        int res = ;
        bool flag = false;   // 找到标记为true
        while(head != nullptr){
            auto it = s.find(head->val);
            if(it != s.end()){   // 找到了
                flag = true;
            }else{               // 没找到,前面的作为一个组件
                if(flag){ res++; }
                flag = false;
            }
            head = head->next;
        }
        if(flag) res++;
        return res;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/linked-list-components

【LeetCode #92】反转链表 II

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

说明: 1 ≤ m ≤ n ≤ 链表长度。

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* pre = dummy;
        for(int i = ; i < m; i++){
            pre = pre->next;
        }
        head = pre->next;
        for(int i = m; i < n; i++){
            ListNode* tmp = head->next;
            head->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp; 
        }
        return dummy->next;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list-i

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表问题-LeetCode 206、234、160(反转,回文,公共结点)

    示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    算法工程师之路
  • 每日算法题:Day 27(机器学习)

    请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符...

    算法工程师之路
  • 每日算法题:Day 18(概率统计)

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的...

    算法工程师之路
  • 两两交换链表中的节点

    一份执着✘
  • Leetcode 24. Swap Nodes in Pairs

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 142 Linked List Cycle II

    Given a linked list, return the node where the cycle begins. If there is no cyc...

    triplebee
  • 剑指Offer LeetCode 面试题18. 删除链表的节点

    输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该...

    TrueDei
  • Leetcode 82 Remove Duplicates from Sorted List II

    Given a sorted linked list, delete all nodes that have duplicate numbers, leavi...

    triplebee
  • 删除链表中的元素

    一份执着✘
  • LintCode-452.删除链表中的元素

    给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5。

    悠扬前奏

扫码关注云+社区

领取腾讯云代金券