最近在刷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的更多相关文章
-
关于Leetcode上二叉树的算法总结
二叉树,结构很简单,只是比单链表复杂了那么一丢丢而已.我们先来看看它们结点上的差异: /* 单链表的结构 */ struct SingleList{ int element; struct Singl ...
-
leetcode top 100 题目汇总
首先表达我对leetcode网站的感谢,与高校的OJ系统相比,leetcode上面的题目更贴近工作的需要,而且支持的语言广泛.对于一些比较困难的题目,可以从讨论区中学习别人的思路,这一点很方便. 经过 ...
-
leetcode上题目的分类
leetcode链表部分题目 https://zhuanlan.zhihu.com/p/29800285 <[Leetcode][链表]相关题目汇总/分析/总结> leetcode堆部分题 ...
-
LeetCode之链表总结
链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度.作为一种常用的数据结构,链表内置在很多高级编程语言里面.既比数组复杂又比树简单,所以链表经常被面试官 ...
-
leetcode - 位运算题目汇总(下)
接上文leetcode - 位运算题目汇总(上),继续来切leetcode中Bit Manipulation下的题目. Bitwise AND of Numbers Range 给出一个范围,[m, ...
-
面试大总结:Java搞定面试中的链表题目总结
package LinkedListSummary; import java.util.HashMap; import java.util.Stack; /** * http://blog.csdn. ...
-
(转)面试大总结之一:Java搞定面试中的链表题目
面试大总结之一:Java搞定面试中的链表题目 分类: Algorithm Interview2013-11-16 05:53 11628人阅读 评论(40) 收藏 举报 链表是面试中常出现的一类题目, ...
-
[LeetCode] 动态规划入门题目
最近接触了动态规划这个厉害的方法,还在慢慢地试着去了解这种思想,因此就在LeetCode上面找了几道比较简单的题目练了练手. 首先,动态规划是什么呢?很多人认为把它称作一种"算法" ...
-
Leetcode解题-链表(2.2.0)基础类
1 基类的作用 在开始练习LeetCode链表部分的习题之前,首先创建好一个Solution基类,其作用就是: Ø 规定好每个子Solution都要实现纯虚函数test做测试: Ø 提供了List ...
随机推荐
-
读书笔记--SQL必知必会--常用MySQL(MariaDB)命令
DBMS信息 显示DBMS的版本 select version(); 显示DBMS状态 status; 显示DBMS资源状态 show status; 显示DBMS支持的权限 show privile ...
-
【每天一题ACM】 斐波那契数列(Fibonacci sequence)的实现
最近因为一些原因需要接触一些ACM的东西,想想写个blog当作笔记吧!同时也给有需要的人一些参考 话不多说,关于斐波那契数列(Fibonacci sequence)不了解的同学可以看看百度百科之类的, ...
-
WPF常用数据绑定控件集合
1.怎么用ListView控件把XML中的数据在界面上显示出来? <?xml version="1.0" encoding="utf-8" ?> & ...
-
Node.js异步处理CPU密集型任务
Node.js异步处理CPU密集型任务 Node.js擅长数据密集型实时(data-intensive real-time)交互的应用场景.然而数据密集型实时应用程序并非仅仅有I/O密集型任务,当碰到 ...
-
[poj1094]Sorting It All Out_拓扑排序
Sorting It All Out poj-1094 题目大意:给出一些字符串之间的大小关系,问能否得到一个唯一的字符串序列,满足权值随下标递增. 注释:最多26个字母,均为大写. 想法:显然,很容 ...
-
RHEL6下获取安装包(RPM)而不安装的方法
RHEL6下获取安装包(RPM)而不安装的方法 有时候我们只能在某个机器上网获得RPM安装包,如何将RPM包在不能上网的内网机器安装,就需要能将安装包下载到本地而不安装,然后再把这些包复制到内网机器, ...
-
D9 图论综合题
1.白银莲花池 LUOGU 2411 第一种思路:当然我们可以写三个bfs a掉这个题,这写下来一二百行要有了吧: 第二种:我们可以在一个bfs中维护所有的信息,一个方向数组,从起点开始,向八个方向扩 ...
-
怎样用命令行开启或关闭Windows服务
怎样用命令行开启或关闭Windows服务 本篇博客主要包含一个内容: 怎样用命令行开启或关闭Windows服务 闲话少叙,直奔主题. 1.在桌面右击新建一个文本文档,然后打开. 2.找到需要开启或关闭 ...
-
rabbitmq级联之shovel插件和exchange.bind
有时候,由于各方面原因比如安全原因.系统间隔离,我们需要实现在多个rabbitmq实例或者一个rabbitmq实例的多个vhost间推送消息.在上一版的实现中,公司使用java自行实现了一个类似转发器 ...
-
在 Azure Resource Manager 中为虚拟机设置密钥保管库
Note Azure 具有两种不同的部署模型,用于创建和处理资源:Resource Manager 模型和经典模型.本文介绍使用 Resource Manager 部署模型.Azure 建议对大多数新 ...