数据结构(data structure)（2）链表的运用

桶排序

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;
    }
    }
}