707. 设计链表

分析

其实写起来很简单，没有什么技巧，就是对编程能力的检查，可以不用任何技巧，但是如果要做好，也有值得注意的技巧
链表相关技巧

因为设计删除操作，所以可以内置虚拟头部，方便操作
内置链表长度的变量，有了这个变量，就可以直接通过 for 循环（循环变量小于链表长度）找到对应位置的元素，不需要判断节点的 next 指针为空，因为只要下标是在长度内的元素，next 都是有值的，可直接使用，这样在特定的位置添加或者删除元素就会很容易，所以这个长度变量的引入减少了判断，对于链表，应该有机会就引入这个变量。
一个完整的链表类，只需要三个方法：增删查：get(index)、add(index,val)、del(index,val) 。其他方法都是这几个方法的特殊化，而 add(index,val)、del(index,val) 方法都是先 get(index) 到要操作的节点，然后再进行操作（这一点在双链表写法中体现的尤为明显），所以实际上，链表操作的核心就是查询方法。
在设计方法的时候，只要有索引参数，就需要检验索引的范围

解题

我的初始版本的解法，凭感觉写的，没有什么规划

class MyLinkedList {
    private ListNode dummyHead;
    public MyLinkedList() {
        // 虚拟节点
        dummyHead = new ListNode(-1,null);
    }

    private ListNode getNode(int index){
	    if(index<0){
		    return null;
	    }
        ListNode targetNode = null;
        ListNode nowNode = dummyHead.next;
        int nowIndex=0;
        while(true){
            if(nowNode==null ){
                break;
            }
            if(nowIndex==index){
                targetNode = nowNode;
                break;
            }
            nowIndex++;
            nowNode=nowNode.next;
        }
        return targetNode;
    }

    public int get(int index) {
        ListNode targetNode = getNode(index);
        return targetNode == null ? -1 : targetNode.val;
    }

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val,dummyHead.next);
        dummyHead.next=newHead;
    }

    public void addAtTail(int val) {
        ListNode tailNode = new ListNode(val,null);
        ListNode nowNode = dummyHead;
        while(true){
            if(nowNode.next==null){
                nowNode.next = tailNode;
                break;
            }else{
                nowNode=nowNode.next;
            }
        }
    }

    public void addAtIndex(int index, int val) {
		if(index<0){
		    return ;
	    }
        //等于0的情况得单独考虑
        if(index==0){
            addAtHead(val);
            return;
        }
        ListNode preNode = getNode(index-1);
        if(preNode!=null){
            ListNode oldNext = preNode.next;
            ListNode tailNode = new ListNode(val,oldNext);
            preNode.next =tailNode;
        }
    }

    public void deleteAtIndex(int index) {
	    if(index<0){
		    return ;
	    }
        //等于0的情况得单独考虑
        if(index==0){
            // 有没有头节点
            ListNode trueHead = getNode(0);
            if(trueHead!=null){
                dummyHead.next = trueHead.next;
            }
        }

        ListNode preNode = getNode(index-1);
        if(preNode!=null){
            ListNode targetNode = preNode.next;
            if(targetNode!=null){
                preNode.next =targetNode.next;
            }
        }
    }

    static class ListNode{
        int val;
        ListNode next;
        public ListNode(){
        }

        public ListNode(int val,ListNode next){
            this.val=val;
            this.next=next;
        }
    }
}

实际上我们经过梳理，可以发现一个完整的链表类，只需要三个方法：增删查：get(index)、add(index,val)、del(index,val) 其他方法都是这几个方法的特殊化，而 add(index,val)、del(index,val) 方法都是先 get(index) 到要操作的节点，然后再进行操作（这一点在双链表写法中体现的尤为明显），所以实际上，链表操作的核心就是查询方法。

/**  
 * 单链表实现  
 * <p>  
 * 实际上一个完成的链表类，只需要三个方法：增删查  
 * get(index)  
 * add(index,val) * del(index,val) * 其他方法都是这几个方法的特殊化  
 */  
class MyLinkedList {  
  
    //如何设置初始值，不如直接内置一个虚拟头节点 dummyHead，所有的遍历都从dummyHead 开始  
    private ListNode dummyHead = new ListNode(-1);  
  
    //需要长度变量  
    private int listLength = 0;  
  
    public MyLinkedList() {  
    }  
    /**  
     * 只要有索引参数，就需要对索引范围进行限定  
     *  
     * @param index  
     * @return  
     */  
    public ListNode getNode(int index) {  
        if (index < 0 || index >= listLength) {  
            return null;  
        }  
        // 遍历代码的模板，now从dummyHead开始，i从-1开始计数  
        ListNode now = dummyHead;  
        // i为 now 在输出的结果数组中的下标，方便和输出参数对应  
        int i = -1;  
        while (now != null) {  
            if (i == index) {  
                break;  
            }  
            now = now.next;  
            i++;  
        }  
        return now;  
    }  
  
    /**  
     * 在链表中的第 index 个节点之前添加值为 val 的节点。  
     * 如果 index 等于链表的长度，则该节点将附加到链表的末尾。  
     * 如果 index 大于链表长度，则不会插入节点。  
     * 如果index小于0，则在头部插入节点。  
     *  
     * @param index  
     * @param val  
     */  
    public void addNodeAtIndex(int index, int val) {  
        if (index > listLength) {  
            return;  
        }  
  
        ListNode node = new ListNode(val);  
  
        if (index <= 0) {  
            index = 0;  
        }  
  
        if (index == listLength) {  
            ListNode tailNode = getNode(listLength - 1);  
            tailNode.next = node;  
            listLength++;  
            return;  
        }  
  
        ListNode now = dummyHead;  
        // 其实这里也可以直接使用 getNode(index-1)获取待插入位置的前一个结点
        // i为 now 在输出的结果数组中的下一个下标，方便和输出参数对应  
        // 此时，now为添加位置的前一个节点  
        int i = 0;  
        while (now != null) {  
            if (i == index) {  
                //上一个下节点  
                ListNode preNext = now.next;  
                now.next = node;  
                node.next = preNext;  
                listLength++;  
                break;  
            }  
            now = now.next;  
            i++;  
        }  
    }  
  
    public void deleteNodeAtIndex(int index) {  
        if (index < 0 || index >= listLength) {  
            return;  
        }  
        ListNode preNode = null;  
        ListNode now = dummyHead;  
        // 此时，now为被删除位置的节点  
        int i = -1;  
        while (now != null) {  
            if (i == index) {  
                preNode.next = now.next;  
                listLength--;  
                break;  
            }  
            preNode = now;  
            now = now.next;  
            i++;  
        }  
    }  
  
    public int get(int index) {  
        int val = -1;  
        if (getNode(index) != null) {  
            val = getNode(index).val;  
        }  
        return val;  
    }  
  
    public void addAtHead(int val) {  
        addAtIndex(0, val);  
    }  
  
    public void addAtTail(int val) {  
        addAtIndex(listLength, val);  
    }  
  
    public void deleteAtIndex(int index) {  
        deleteNodeAtIndex(index);  
    }  
  
    public void addAtIndex(int index, int val) {  
        addNodeAtIndex(index, val);  
    }  
  
    public class ListNode{  
        int val;  
        ListNode next;  
  
        public ListNode(){}  
  
        public ListNode(int val){  
            this.val = val;  
        }  
  
        public ListNode(int val,ListNode next){  
            this.val = val;  
            this.next = next;  
        }  
  
    }  
}

此外还有双向链表的解法，这里就不赘述了，具体请看代码随想录

707. 设计链表

分析

解题

相关题