关于LeetCode上链表题目的一些trick

时间:2022-09-13 17:01:02

最近在刷leetcode上关于链表的一些高频题,在写代码的过程中总结了链表的一些解题技巧和常见题型。

结点的删除

指定链表中的某个结点,将其从链表中删除。

由于在链表中删除某个结点需要找到该结点的前一个位置,然后将前一个结点的next指针直接绕过该结点即可删除。但找到该结点的前一个位置需要指针遍历,其实还有一种更简单的trick,就是将要删除的结点的值设为该结点的后一个的值,然后删除该结点的后一个结点(间接删除,不需要找遍历前一个指针),代码如下:

class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}

在表头前增加虚拟结点

很多场合下,在链表的表头前增加一个虚拟结点(dummy),并让其指向head,能简化很多操作。如在新创建一个链表或对链表进行遍历操作时,如果不增加虚拟结点,就需要处理当前结点是头结点的特殊情况(因为头结点前没有其他结点,导致操作代码不一致)。加了虚拟结点后就可以像操作其他结点一样对待头结点了,最后只需要返回虚拟结点的next就可以了。

如LeetCode上的这一题:Remove Nth Node From End of List

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = dummy;
ListNode q = dummy;
while(n > 0) {
q = q.next;
n--;
} while(q.next != null) {
p = p.next;
q = q.next;
}
p.next = p.next.next; return dummy.next;
}
}

链表转置

这应该是我碰到的链表中最频繁的问题了,很多其他链表的题目可能也需要借助于链表转置这一功能,所以需要能够熟练地写出代码,这里给出包括迭代和递归两种版本的代码:

class Solution {
//迭代实现链表转置
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
} //递归实现链表转置
public ListNode reverseList2(ListNode head) {
if(head == null || head.next == null)
return head; ListNode next = head.next;
//对head.next执行转置
ListNode newHead = reverseList(next);
//此时next变成了转置后的尾结点
next.next = head;
head.next = null;
return newHead;
}
}

快慢双指针

有时候需要找到链表的中间位置的结点,这时就需要设置两个指针slow和fast,slow每次往前移动一个,fast移动两个。当fast为空时,slow就指向了链表的中间位置。比如leetcode上的Palindrome Linked List在判断链表是否回文时,需要找到中间位置,然后将其后半部分转置和前半部分相比较,具体实现代码如下:

class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
} //注意不能直接转置整个链表,需要找到链表的中间,只转置后半部分
ListNode fast = head, slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//这时slow指向了链表的中间结点(注意这种trick要记住)
slow = reverseList(slow);
while(head != null && slow != null) {
if(head.val != slow.val) {
return false;
}
head = head.next;
slow = slow.next;
} return true;
} private ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}

合并两个有序链表

这也是碰到的很常见的问题了,合并两个有序链表使其仍然保持有序,一般采用双指针法,这也需要能够熟练地写出无bug的代码来。这里给出迭代和递归两种实现方式:

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) {
return null;
} ListNode p = l1;
ListNode q = l2;
ListNode dummy = new ListNode(0);
ListNode pp = dummy;
while(p != null && q != null) {
if(p.val < q.val) {
dummy.next = new ListNode(p.val);
p = p.next;
}
else {
dummy.next = new ListNode(q.val);
q = q.next;
}
dummy = dummy.next;
} if(p != null) {
//直接将dummy指过去
dummy.next = p;
} if(q != null) {
dummy.next = q;
} return pp.next;
} //使用递归更简单
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1; if(l1.val<l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}

目前碰到的问题就这么多了,后面再继续补充吧。

关于LeetCode上链表题目的一些trick的更多相关文章

  1. 关于Leetcode上二叉树的算法总结

    二叉树,结构很简单,只是比单链表复杂了那么一丢丢而已.我们先来看看它们结点上的差异: /* 单链表的结构 */ struct SingleList{ int element; struct Singl ...

  2. leetcode top 100 题目汇总

    首先表达我对leetcode网站的感谢,与高校的OJ系统相比,leetcode上面的题目更贴近工作的需要,而且支持的语言广泛.对于一些比较困难的题目,可以从讨论区中学习别人的思路,这一点很方便. 经过 ...

  3. leetcode上题目的分类

    leetcode链表部分题目 https://zhuanlan.zhihu.com/p/29800285 <[Leetcode][链表]相关题目汇总/分析/总结> leetcode堆部分题 ...

  4. LeetCode之链表总结

    链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度.作为一种常用的数据结构,链表内置在很多高级编程语言里面.既比数组复杂又比树简单,所以链表经常被面试官 ...

  5. leetcode - 位运算题目汇总&lpar;下)

    接上文leetcode - 位运算题目汇总(上),继续来切leetcode中Bit Manipulation下的题目. Bitwise AND of Numbers Range 给出一个范围,[m, ...

  6. 面试大总结:Java搞定面试中的链表题目总结

    package LinkedListSummary; import java.util.HashMap; import java.util.Stack; /** * http://blog.csdn. ...

  7. &lpar;转&rpar;面试大总结之一:Java搞定面试中的链表题目

    面试大总结之一:Java搞定面试中的链表题目 分类: Algorithm Interview2013-11-16 05:53 11628人阅读 评论(40) 收藏 举报 链表是面试中常出现的一类题目, ...

  8. &lbrack;LeetCode&rsqb; 动态规划入门题目

    最近接触了动态规划这个厉害的方法,还在慢慢地试着去了解这种思想,因此就在LeetCode上面找了几道比较简单的题目练了练手. 首先,动态规划是什么呢?很多人认为把它称作一种"算法" ...

  9. Leetcode解题-链表&lpar;2&period;2&period;0&rpar;基础类

    1 基类的作用 在开始练习LeetCode链表部分的习题之前,首先创建好一个Solution基类,其作用就是: Ø  规定好每个子Solution都要实现纯虚函数test做测试: Ø  提供了List ...

随机推荐

  1. 读书笔记--SQL必知必会--常用MySQL(MariaDB)命令

    DBMS信息 显示DBMS的版本 select version(); 显示DBMS状态 status; 显示DBMS资源状态 show status; 显示DBMS支持的权限 show privile ...

  2. 【每天一题ACM】 斐波那契数列(Fibonacci sequence)的实现

    最近因为一些原因需要接触一些ACM的东西,想想写个blog当作笔记吧!同时也给有需要的人一些参考 话不多说,关于斐波那契数列(Fibonacci sequence)不了解的同学可以看看百度百科之类的, ...

  3. WPF常用数据绑定控件集合

    1.怎么用ListView控件把XML中的数据在界面上显示出来? <?xml version="1.0" encoding="utf-8" ?> & ...

  4. Node&period;js异步处理CPU密集型任务

    Node.js异步处理CPU密集型任务 Node.js擅长数据密集型实时(data-intensive real-time)交互的应用场景.然而数据密集型实时应用程序并非仅仅有I/O密集型任务,当碰到 ...

  5. &lbrack;poj1094&rsqb;Sorting It All Out&lowbar;拓扑排序

    Sorting It All Out poj-1094 题目大意:给出一些字符串之间的大小关系,问能否得到一个唯一的字符串序列,满足权值随下标递增. 注释:最多26个字母,均为大写. 想法:显然,很容 ...

  6. RHEL6下获取安装包&lpar;RPM&rpar;而不安装的方法

    RHEL6下获取安装包(RPM)而不安装的方法 有时候我们只能在某个机器上网获得RPM安装包,如何将RPM包在不能上网的内网机器安装,就需要能将安装包下载到本地而不安装,然后再把这些包复制到内网机器, ...

  7. D9 图论综合题

    1.白银莲花池 LUOGU 2411 第一种思路:当然我们可以写三个bfs a掉这个题,这写下来一二百行要有了吧: 第二种:我们可以在一个bfs中维护所有的信息,一个方向数组,从起点开始,向八个方向扩 ...

  8. 怎样用命令行开启或关闭Windows服务

    怎样用命令行开启或关闭Windows服务 本篇博客主要包含一个内容: 怎样用命令行开启或关闭Windows服务 闲话少叙,直奔主题. 1.在桌面右击新建一个文本文档,然后打开. 2.找到需要开启或关闭 ...

  9. rabbitmq级联之shovel插件和exchange&period;bind

    有时候,由于各方面原因比如安全原因.系统间隔离,我们需要实现在多个rabbitmq实例或者一个rabbitmq实例的多个vhost间推送消息.在上一版的实现中,公司使用java自行实现了一个类似转发器 ...

  10. 在 Azure Resource Manager 中为虚拟机设置密钥保管库

    Note Azure 具有两种不同的部署模型,用于创建和处理资源:Resource Manager 模型和经典模型.本文介绍使用 Resource Manager 部署模型.Azure 建议对大多数新 ...