链表

链表

• 真正的动态,不需要处理固定容量的问题
• 丧失了随机访问的能力

实现

public class LinkedList{
    
    private class Node{
        public Integer e;
        public Node next;

        public Node(Integer e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(Integer e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }
    }

    // 虚拟头节点
    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead = new Node(null,null);
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void addFirst(Integer e){
        add(0,e);
    }

    public void add(int index, Integer e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index");
        }
        Node prev = dummyHead;
        for(int i=0; i<index; i++){
            prev = prev.next;
        }
        prev.next = new Node(e,prev.next);
        size ++;
    }

    public void addLast(Integer e){
        add(size,e);
    }

    public Integer get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Get failed. Illegal index");
        }
        Node cur = dummyHead.next;
        for(int i=0; i<index; i++){
            cur = cur.next;
        }
        return cur.e;
    }

    public Integer getFirst(){
        return get(0);
    }

    public Integer getLast(){
        return get(size-1);
    }

    public void set(int index, Integer e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Set failed. Illegal index");
        }
        Node cur = dummyHead.next;
        for(int i=0; i<index; i++){
            cur = cur.next;
        }
        cur.e = e;
    }

    public boolean contains(Integer e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public Integer remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Set failed. Illegal index");
        }
        Node prev = dummyHead;
        for(int i=0; i<index; i++){
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;
        return retNode.e;
    }
}

链表问题

1.删除链表中指定的所有元素

class Solution{ 
    public ListNode removeElements(ListNode head, int val){
        while(head != null && head.val == val){
            ListNode delNode = head;
            head = delNode.next;
            delNode = null;
        }
        if(head == null){
            return head;
        }

        ListNode prev  = head;
        while(prev.next != null){
            if(prev.next.val == val){
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else{
                prev = prev.next;
            }
        }
        return head;
    }

    // 递归解决
    public ListNode removeElements2(ListNode head, int val){
        if(head == null){
            return head;
        }
        ListNode res = removeElements2(head.next, val);
        if(head.val == val){
            return res;
        }else{
            head.next = res;
            return head;
        }
    }
}

2.反转链表

class Solution{
    public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 递归实现
    public ListNode reverseList2(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode rev = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return rev;
    }
}