桶排序
e*len/(max+1) e为每个元素,根据上式判断该元素放入哪个桶 桶排序适用于分布均匀的数组 1.arr->length,max 2.Node[]-new Node[length] 3.扫描->hash->下标->元素入桶 4.出桶<=>排序排序的输出 private void sort(int[] arr){ int length=arr.length; LinkedNode[] bucket=new LinkedNode[length];//桶的数等于length int max=Util.maxOf(arr);//求max //入桶 for(int i=0;i<length;i++){ int value=arr[i];//扫描每个元素 int hash=hash(arr[i],max,length);//桶的下标 if(bucket[hash]==null){//初始化链表表头 bucket[hash]=new LinkedNode(value); }else{ insertInto(value,bucket[hash],bucket,hash);//插入链表 } } int k=0;//记录数组下标 //出桶 for(LinkedNode node:bucket){ if(node!=null){ while(node!=null){//遍历整个桶 arr[k++]=node.value; node=node.next; } } } } private void insertInto(int value,LinkedNode head,LinkedNode[] bucket,int hash){ LinkedNode newNode=new LinkedNode(value); //小于头节点,放在头上 if(value<=head.value){ //替换头节点 bucket[hash]=newNode; return; } //往后找第一个比当前值大的结点,放在这个结点的前面 LinkedNode p=head; LinkedNode pre=p; while(p!=null&&value>p.value){ pre=p; p=p.next; } if(p==null){//搜到末尾了 pre.next=newNode; }else{//插入pre和p之间 pre.next=newNode; newNode.next=p; } }
删除重复元素
//创建链表 //单向链表 class Node{ Node next=null; int data; public Node(int d){ data=d; } } void appendToTail(int d){ Node end=new Node(d); Node n=this; while(n.next!=null){ n=n.next; } n.next=end; }
移除未排序链表中的重复部分
拉链法 散列=hash 若hash表已经标记过,就删除 public class RemovRepeation{ public static void main(String[] args){ int[] data={1,6,7,3,6}; Node head=new Node(null); Node p=head; for(int i=0;i<data.length;i++){ p.next=new Node(data[i]); p=p.next; } rr(head);//移除重复 Node p1=head.next; while(p1!=null){ System.out.println(p1.value); p1=p1.next; } private static void rr(Node head){ HashSet set=new HashSet(); Node pre=head; Node p1=head.next; while(p1!=null){ if(set.contains(p1.value)){//存在,说明重复->删除 pre.next=p1.next; }else{ set.add(p1.data); } p1=p1.next; } } private static class Node{ Node next; Object value; public Node(Object value){ this.value=value; } } }
删除倒数第k个元素
public class KtNode{ //特别要注意边界地问题 public ListNode FindeKthToTail(ListNode head,int k){ if(head==null||k<=0){ return null; } ListNode p1=head; ListNode p2-head; int count=0; while(count<k){//先让p2到第k+1个结点上 p2=p2.next; count++; } while(p2!=null){//两个指针相差k个结点距离 p1=p1.next;//两指针同时平移 p2=p2.next;//当p2到null,p1就到了倒数第k个结点 } System.out.println(p1.val); return p1; } public static void main(String[] args){ int[] arr={1,2,3,4,5} ListNode head=new ListNode(0); for(int i=0;i<arr.length;i++){ p.next=new ListNode(arr[i]); p=p.next; } System.out.println(head); obj.FindKthToTail(head,3); } }
删除单项链表中的某节点
若该节点为尾结点,返回false,否则true public class _2_3RemoveNode3{ public boolean removeNode(ListNode pNode){ if(pNode next==null){ return false; pNode.val=pNode.next.val;//复制后继的内容 pNode.next=pNode.next.next;//跨越后继 return true; } } }
以给定值x为基准将链表分割为两部分,所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针ListNode* pHead,请返回重新排列后的链表的头指针
注意分割后 2->3->4->5->6 2->1->3->5->6 L-head L-tail r-head r-tail public ListNode parttition(ListNode pHead,int x){ ListNode leftTail=null; ListNode rightTail=null; ListNode p=pHead; ListNode leftFirst=null; ListNode rightFirst=null; while(p!=null){//顺序扫描所有结点 · int pValue=p.val; if(pvalue<x){//小于x if(leftTail==null){ leftFirst=p; leftTail=p; }else{ leftTail.next=p; leftTail=leftTail.next; } }else{//大于x if(rightTail==null){ rightFirst=p; rightTail=p; }else{ rightTail.next=p; rightTail=rightTail.next; } } p=p.next; } if(leftFirst==null){//左边链表可能为空 return rightFirst; } leftTail.next=rightFirst;//左右两个链表连接起来 if(rightTail!=null){ rightTail.next=null; } return leftFirst; }
有两个用链表来表示的整数,每个结点包含一个数位
这些数位是反向存放的,也就是个位排在链表的首位,编写函数对这两个整数求和
给定两个链表ListNode* A ListNode* B请返回A+B的结果(ListNode*) public ListNode plusAB(ListNode a,ListNode b){return plusAB(a,b,0);} public ListNode plusAB(ListNode a,ListNode b,int i){ if(a==null&&b==null&&i==0) return null; int value=i; if(a!=null){ value+=a.val; } if(b!=null){ value+=b.val; } ListNode result=new ListNode(value%10); result.next=plusAB(a==null?null:a.next,b==null?null:b.next,value>=10?1:0) //递归链表 return result; }
给定一个有环链表,实现一个算法返回环路的开头结点
有环链表的定义 在链表中某个结点的next元素指向在它前面出现过的结点则表明该链表存在环路 HashSet判断重复,判断元素是否存在 hash-equeal public ListNode check(ListNode head){ ListNode p=head;//传一个链表 HashSet set=new HashSet();//hashset while(true){ if(set.contains(p))return p;//遍历链表,如果存在相同结点,则退出 else{set.add(p);p=p.next;}//不存在相同结点,则加入hashset,链表继续往下面遍历 } } 快慢指针 S一步一进,f两步一进=》s,f相遇于某一点 如果存在环,必定在某一点相遇,若是没有环,则不相遇 public boolean hashCircle(ListNode head){ ListNode s=head; ListNode f=head; while(true){ s=s.next; f=f.next.next; if(s==f)return true; if(s==null||f==null||f.next==null) return false; } } s和f相聚于何处 f差l-k步 s走l-k步后相遇 他们离的起点还有k步 public ListNode beginOfCircle(ListNode head){ ListNode s=head; ListNode f=head; while(f!=null&&f.next!=null){ s=s.next; f=f.next.next; if(s==f) break; } //何种方式退出的? if(f==null||f.next==null){ return null; ` } ListNode p=head; while(p!=s){ p=p.next; s=s.next; } return p; }
回文链表
检查链表是否回文 翻转链表 a->b->c->b->a a b c c b a 借助栈,一半入栈,一半匹配出栈 前半部分压栈 public boolean isPalindrome(ListNnode,pHead){ if(pHead==null){ return false; } if(pHead.next=null){ return true; } ListNode slower=pHead; ListNode faster=pHead; Stack<ListNode>stack=new Stack<>(); boolean isOdd=true; while(faster!=null&&faster.next!=null){ stack.push(slower);//压栈 slower=slower.next; faster=faster.next.next; if(faster==null){ isOdd=false; } } //奇数个结点,slower还要next一下 if(isOdd) slower=slower.next; while(!stack.empty()){ if(stack.pop().val!=slower.val){ return false; }else{ slower=slower.next; } } }