题目链接:https://www.hackerrank.com/challenges/almost-sorted-interval 题目大意: 定义一个“几乎单调”区间(区间最小值在最左面,最大值在最右面) 给一个N的排列,求“几乎单调”区间的个数 N=100W  解法为O(n) 很好的思维题! 想了一下午,其实自己离正解已经不远了,,不过最后还是看了学长的ac代码 然后基本上秒懂了 具体思维方式不好说啊..贴个代码,以后又不会了的话慢慢回忆吧= =|| #include <iostream>

package LinkedListSummary; import java.util.HashMap; import java.util.Stack; /** * http://blog.csdn.net/luckyxiaoqiang/article/details/7393134 轻松搞定面试中的链表题目 * http://www.cnblogs.com/jax/archive/2009/12/11/1621504.html 算法大全(1)单链表 * * 目录: * 1. 求单链表中结点的个

面试大总结之一:Java搞定面试中的链表题目 分类: Algorithm Interview2013-11-16 05:53 11628人阅读 评论(40) 收藏 举报 链表是面试中常出现的一类题目,本文用Java实现了面试中常见的链表相关题目.本文主要参考整合重写了<轻松搞定面试中的链表题目>和 <算法大全(1)单链表>两篇大作.两篇大神的实现分别是C和C#,因为我更喜欢用Java面试,所以用Java重写了所有实现,并附上自己的一些思考注释.算法大全(1)单链表 尚未有一些问题尚

最近在刷leetcode上关于链表的一些高频题,在写代码的过程中总结了链表的一些解题技巧和常见题型. 结点的删除 指定链表中的某个结点,将其从链表中删除. 由于在链表中删除某个结点需要找到该结点的前一个位置,然后将前一个结点的next指针直接绕过该结点即可删除.但找到该结点的前一个位置需要指针遍历,其实还有一种更简单的trick,就是将要删除的结点的值设为该结点的后一个的值,然后删除该结点的后一个结点(间接删除,不需要找遍历前一个指针),代码如下: class Solution { public

2014-03-18 02:57 题目:检查链表是否是回文的,即是否中心对称. 解法:我的做法是将链表从中间对半拆成两条,然后把后半条反转,再与前半条对比.对比完了再将后半条反转了拼回去.这样不涉及额外的空间,比反转整条链表然后比较要来的好.如果你反转了整条链表又不用额外空间,接下来跟谁比去呢? 代码: // 2.7 To Check the given linked list is palindrome or not? #include <cstdio> #include <unord

2014-03-18 02:41 题目:给定一个带有环的单链表,找出环的入口节点. 解法1:用hash来检测重复节点肯定是容易想而且效率也高的好办法. 代码: // 2.6 You have a circular Linked List: a->b->c->d->e->c. Find where the cycle starts. #include <cstdio> #include <unordered_set> using namespace st

2014-03-18 02:32 题目:给定两个由单链表表示的数字,返回它们的和.比如(9->9) + (1->2) = 0->2->1,99 + 21 = 120. 解法:逐位相加,注意处理进位.长度不等. 代码: // 2.5 Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addi

2014-03-18 02:27 题目:将一个单链表按照一个值X分为两部分,小于X的部分放在大于等于X的部分之前. 解法:按照值和X的大小,分链表为两条链表,然后连起来成一条. 代码: // 2.4 Write code to partition a linked list around a value x, such that all nodes less than x comes before all nodes greater than or equal to x. #include <c

2014-03-18 02:25 题目:给定一个单链表中间的节点,删掉那个节点. 解法:把后面节点的数据域拷到当前节点来,然后删除后面那个节点.当前节点不是尾巴,所以后面不为空. 代码: // 2.2 Remove a node from middle of a linked list #include <cstdio> using namespace std; struct ListNode { int val; struct ListNode *next; ListNode(int x):

2014-03-18 02:24 题目:给定一个单链表,找出倒数第K个节点. 解法:让一个指针先走K步,然后俩指针一起走到尽头.当然也可以先走到尽头数出链表的长度,然后第二次少走K步.其实耗费的工夫是一样的,但貌似总有人觉得第一种方法很巧妙很优美. 代码: // 2.2 Remove a node from middle of a linked list #include <cstdio> using namespace std; struct ListNode { int val; stru

2014-03-18 02:16 题目:给定一个未排序的单链表,去除其中的重复元素. 解法1:不花额外空间,使用O(n^2)的比较方法来找出重复元素. 代码: // 2.1 Remove duplicates from a linked list // inefficient without hashing space #include <cstdio> #include <unordered_set> using namespace std; struct ListNode {

最近总结了一下数据结构和算法的题目,这是第二篇文章,关于链表的,第一篇文章关于二叉树的参见 废话少说,上链表的数据结构 class ListNode { ListNode next; int val; ListNode(int x){ val = x; next = null; } } 1.翻转链表 ListNode reverse(ListNode node){ ListNode prev = null; while(node!=null){ ListNode tmp = node.next;

1.从头到尾打印链表 输入一个链表,按链表值从尾到头的顺序返回一个ArrayList. # -*- coding:utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def printListFromTailToHead(self, listNode): l =[] while listNode: l.append(listNode.val) listNode

本篇延续上一篇剑指offer题目系列二,介绍<剑指offer>第二版中的四个题目:O(1)时间内删除链表结点.链表中倒数第k个结点.反转链表.合并两个排序的链表.同样,这些题目并非严格按照书中的顺序展示的,而是按自己学习的顺序,每个题目包含了分析和代码. 9.O(1)时间内删除链表结点 题目: 在O(1)时间内删除链表结点.给定单链表的头指针和一个结点指针,定义一个方法在O(1)时间内删除该结点. 单链表的定义如下: 解答: 单向链表删除一个结点,最直观的想法是从链表的头结点开始顺序遍历查找要

一.题目:从尾到头打印链表 题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值. 到解决这个问题肯定要遍历链表.遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头.也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出.这就是典型的“后进先出”,我们可以用栈实现这种顺序. 二.解题思路 每经过一个结点的时候,把该结点放到一个栈中.当遍历完整个链表后,再从栈顶开始逐个输出结点的值,此时输出的结点的顺序已经反转过来了. 三.解决问题 3.1 代码实现 这里使用的是自定义

一.题目:反转链表 题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点. 链表结点定义如下,这里使用的是C#描述: public class Node { public int Data { get; set; } // 指向后一个节点 public Node Next { get; set; } public Node(int data) { this.Data = data; } public Node(int data, Node next) { this.Dat

PS:这也是一道出镜率极高的面试题,我相信很多童鞋都会很眼熟,就像于千万人之中遇见不期而遇的人,没有别的话可说,唯有轻轻地问一声:“哦,原来你也在这里? ” 一.题目:合并两个排序的链表 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的.例如输入下图中的链表1和链表2,则合并之后的升序链表如链表3所示. 链表结点定义如下,使用C#描述: public class Node { public int Data { get; set; } // 指向后一个节点 pu

前言 最近准备暑假回家回家修整一下,所以时间大部分用来完成项目上的工作,同时为了9月份的校招,晚上的时间我还在学习<cracking the coding intreview>,第二章链表有几个不错的题目,记录一下   单链表 题目: Implement an algorithm to find the nth to last element of a singly linked list. 译文: 实现一个算法从一个单链表中返回倒数第n个元素 思路 7个节点的示例链表图如下: 例如我们找倒数

[还有一些其他的算法提]http://blog.csdn.net/WalkingInTheWind/article/category/906980 [转]http://blog.csdn.net/lumengjie313/article/details/45667425 package LinkedListSummary; import java.util.HashMap; import java.util.Stack; /** * http://blog.csdn.net/luckyxiaoq

链表作为常考的面试题,并且本身比较灵活,对指针的应用较多.本文对常见的链表面试题Java实现做了整理. 链表节点定义如下: static class Node { int num; Node next; } 全部代码放在 https://github.com/morethink/algorithm/blob/master/src/algorithm/list/LinkedList.java 1. 求单链表中结点的个数 依次遍历链表 public static int size(Node head

206. 反转链表 题目:反转一个单链表. 进阶:链表可以迭代或递归地反转.你能否两个都实现一遍? 非递归代码: class Solution { public ListNode reverseList(ListNode head) { if(head == null) return null; ListNode pre = null, nex = null; while(head != null){ nex = head.next; head.next = pre; pre = head; h