算法第四版链表练习1.3.20

快来打我* 2022-03-19 15:58 104阅读 0赞

# 题目 #

编写一个方法delete()，接受一个int参数k，删除链表的第k个元素（如果它存在的话）。

# 分析 #

比如有链表  
1,2,3,4,5  
如果要删除第四个数据"4"  
那么就把2的next引用到2.next.next就是4…  
如同1.3.18里面的x.next=x.next.next代表删除x的下一个节点,然后把下下个节点接上去

# java代码 #

注意是方法:deleteChoose(int number)

package hk13;
    
    import book1_3.LinkedListBag;
    import edu.princeton.cs.algs4.Stack;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-17
     **/
    public class W_1_3_19 <Item> implements Iterable{
        private class Node{
            Item item;
            Node next;
        }
    
        private Node first;
        private Node last;
        private int n;
    
        public boolean isEmpty() {
            return n == 0;
        }
    
        public int size() {
            return n;
        }
    
        public void push1(Item item) {
            //在集合的头部插入元素
            Node old = first;
            first = new Node();
            first.item = item;
            first.next = old;
    
        }
        public void push2(Item item){
            //在集合的尾部插入元素
            Node old=last;
            last=new Node();
            last.item=item;
            if(isEmpty()){
                first=last;
            }else{
                old.next=last;
            }
    
            n++;
        }
        public Item pop(){
            //从集合的头部取出一个元素
            Item item = first.item;
            first=first.next;
            return item;
        }
        public void deleteLast(){
            Node current=first;
            while(current.next.next!=null){
                current=current.next;
            }
            current.next=null;
        }
        //1.3.20这个方法就是作业
        public void deleteChoose(int number){
            Node current=first;
            if(number==1){
                first=first.next;
            }else{
                for(int i=0;i<number-2;i++){
                    //当number为2的时候,不走循环,为3的时候,走一次循环,为1的时候,就不行了.要走上面那个
                    current=current.next;
                }
                current.next=current.next.next;
            }
        }
    
        @Override
        public Iterator iterator() {
            return new ListIterator();
        }
    
        private class ListIterator implements Iterator<Item> {//注意泛型在后面这里
            private Node current = first;
    
            @Override
            public boolean hasNext() {
                return current != null;
            }
    
            @Override
            public Item next() {
                //后进先出
                Item item = current.item;
                current = current.next;
                return item;
            }
        }
    
        public static void main(String[] args) {
            W_1_3_19<String> stack=new W_1_3_19<String>();
            stack.push1("1");
            stack.push1("2");
            stack.push1("3");
            for (Object s:stack
            ) {
                System.out.println(s);
            }
            stack.deleteLast();
            System.out.println("删除了尾巴的1");
            for (Object s:stack
                 ) {
                System.out.println(s);
            }
            System.out.println("楼上是后进先出,楼下是先进先出");
            W_1_3_19<String> stack2=new W_1_3_19<String>();
            stack2.push2("1");
            stack2.push2("2");
            stack2.push2("3");
            for (Object s:stack2
            ) {
                System.out.println(s);
            }
            stack2.deleteLast();
            System.out.println("删除了尾巴的3");
            for (Object s:stack2
            ) {
                System.out.println(s);
            }
            System.out.println("楼下是题目1.3.20的");
            W_1_3_19<String> stack3=new W_1_3_19<String>();
            stack3.push1("5");
            stack3.push1("4");
            stack3.push1("3");
            stack3.push1("2");
            stack3.push1("1");
            //这里的时候stack3的链表结构是1-2-3-4-5(从头添加元素进去的结果)
            stack3.deleteChoose(2);
            for (Object s:stack3
            ) {
                System.out.println(s);
            }
    
        }
    
    
    }

# 运行结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 心得 #

1,知道循环的次数,就用for循环比较简单  
2,要明白current指向那个节点  
3,当number=1的时候是特殊情况,就用if分开特殊情况处理  
4,当数据结构里面是空的情况就不考虑了

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/966c850aeae74018a70cd78152334756.png