专栏首页落影的专栏程序员进阶之算法练习(五十)LeetCode链表专题

程序员进阶之算法练习(五十)LeetCode链表专题

正文

链表是面试中经常考察的概念,选了4道LeetCode中常见链表题目,难度是Easy和Medium。

1.移除链表第n个节点

题目链接 题目大意: 给出一个链表,删除链表的倒数第n个节点,然后返回链表的头指针。 Example: 给出链表 1->2->3->4->5, and n = 2. 操作后的链表 1->2->3->5.

题目解析: 这里可以分解两个子问题: 1、找到链表倒数第n个点; 2、在链表中删除一个节点;

问题1可以先遍历指针得到节点个数sum,这样可以得到删除的节点为正数的第sum-n+1个节点; 问题2是标准问题,注意next指针的特殊处理;

这里有个trick,如果删除的节点是第一个节点,此时应该返回head->next的节点; 其他情况,类似 1->3->x->4->6,这样的链表,删除中间x点,只需要找到x的上一个节点,使得其next等于x的下一个节点即可。

复杂度解析: 时间复杂度是O(N) 空间复杂度是O(N)

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *tmp = head;
        int count = 1;
        while (tmp->next) {
            tmp = tmp->next;
            ++count;
        }
        int x = count - n + 1;
        
        ListNode *ret = head;
        if (x == 1) {
            ret = head -> next;
        }
        else {
            tmp = head;
            while (x > 2) {
                --x;
                tmp = tmp->next;
            }
            if (tmp->next) {
                tmp->next = tmp->next->next;
            }
            else {
                tmp->next = NULL;
            }
        }
        
        return ret;
    }
};

2.合并两个有序链表

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

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

题目解析: 遍历两个链表,每次从链表中选择一个较小大数字的节点出来,直接两个链表为空; 注意:需要考虑两个链表,部分为空或者全部为空的情况;

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *ret = NULL, *cur = NULL;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                if (!cur) {
                    cur = ret = l1;
                }
                else {
                    cur->next = l1;
                }
                cur = l1;
                l1 = l1->next;
            }
            else {
                if (!cur) {
                    cur = ret = l2;
                }
                else {
                    cur->next = l2;
                }
                cur = l2;
                l2 = l2->next;
            }
        }
        if (l1) {
            if (cur) {
                cur->next = l1;
            }
            else {
                ret = cur = l1;
            }
        }
        else {
            if (cur) {
                cur->next = l2;
            }
            else {
                ret = cur = l2;
            }
        }
        return ret;
    }
}leetcode;

3.两两交换链表中的节点

题目链接 题目大意: 给出一个链表,要求每两个节点做一次节点交换,如果是奇数链表,最后一个节点不用交换; 比如说给出1->2->3->4,要求结果是2->1->4->3; 要求: 1、常数的空间大小; 2、不允许修改链表节点的值,只能修改其next指针;

示例 1:

输入:head = [1,2,3,4] 输出:[2,1,4,3]

示例 2: 输入:head = [] 输出:[]

示例 3: 输入:head = [1] 输出:[1]

题目解析: 假如是数组交换,那么就是a[1]=a[2]这样直接交换即可; 如果允许值修改,同样可以用上面的方案,但这里要求交换节点;

先看直接交换节点的情况:对于节点1和2,直接交换next指针,变成2,1,此时链表是2->1->3->4->NULL; 接着重复上面的过程交换3,4,变成4,3,链表是4->3->NULL,但是此时链表并不是2134; 注意看前面1、2交换后,此时1指向3;当3,4交换完之后,链表就是2-1>3->NULL! 这是题目的第一个trick,解决方案有两种: 1、从倒数开始交换; 2、新增last指针,在每次交换后记录后一个节点,在下一次交换时修改值;比如说在1,2交换后last=1;在交换3,4后,让last->next=4即可;

方案2实现较为简单,增加一个临时变量即可。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *ret = head;
        if (head && head->next) { // null trick
            ret = head->next;
        }
        ListNode *last = NULL;
        while (head && head->next) {
            ListNode *tmp = head->next;
            head->next = tmp->next;
            tmp->next = head;
            // update last
            if (last && last->next) { // null trick
                last->next = tmp;
            }
            last = head;
            
            head = head->next;
        }
        
        return ret;
    }
};

4.旋转链表

题目链接 题目大意: 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

题目解析: 右移k步,假设链表有sum个节点; 先对k处理,k=k%sum,保证k<sum,然后 找到从左到右第k-1个节点p和第k个节点ans,使得p->next=NULL; 然后找到最后一个节点,使得其next等于head; 最后返回ans就好。

复杂度解析: 时间复杂度是O(N) 空间复杂度是O(N)

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int sum = 0;
        ListNode *p = head;
        while (p) {
            p = p->next;
            ++sum;
        }
        if (sum) {
            k = k % sum;
            if (k) { // 保险起见
                k = sum - k; // 从左到右第k个
                p = head;
                ListNode *last = NULL;
                while (k--) {
                    last = p;
                    p = p->next;
                }
                ListNode *ans = p;
                while (p && p->next) {
                    p = p->next;
                }
                if (last) {
                    last->next = NULL;
                }
                if (p) {
                    p->next = head;
                }
                head = ans;
            }
        }
        return head;
    }
}leetcode;

总结

链表的操作要注意边界,非常容易出现越界、next指针没赋值等。 有一个建议是写的时候注意遍历流程,如果需要改动链表节点则记得初始化,适当写一些冗余代码;如果想不清楚可以先画个图,写下伪代码。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的...

    落影
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

    落影
  • 程序员进阶之算法练习(十五)

    前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

    落影
  • 程序员进阶之算法练习(三十四)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

    落影
  • 程序员进阶之算法练习(三十三)LeetCode专场

    BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

    落影
  • 程序员进阶之算法练习(三十三)LeetCode专场

    BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

    落影
  • 程序员进阶之算法练习(三十二)LeetCode专场

    题目链接 题目大意: 给出一个链表RandomListNode *next, *random; 每个节点有int值,有两个指针,一个指向下一个节点,一个指...

    落影
  • 程序员进阶之算法练习(二十五)

    前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

    落影
  • 程序员进阶之算法练习(四十五)

    每个路口的机动车道有三个方向,分别是左转、直行、右转,同时路口有一条人行道; 每行输入有四个数字l,s,r,p,分别表示左转、直行、右转、人行道的交通信号灯是...

    落影

扫码关注云+社区

领取腾讯云代金券