707. 设计链表

leetcode链接：
https://leetcode.cn/problems/design-linked-list/

方案一

注：此方案无法正常执行
原因：底层开始设计出现问题，细节决定成败

class MyLinkedList {

    int val;

    MyLinkedList next;

    MyLinkedList prev;

    boolean numFlag;

    public MyLinkedList() {
        this.next = null;
        this.prev = null;
    }

    public int get(int index) {
        MyLinkedList temp = this;

        for (; index > 0; index--) {
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }

        if (temp == null) {
            return -1;
        } else {
            return temp.val;
        }
    }

    public void addAtHead(int val) {
        if (!numFlag) {
            this.val = val;
            this.numFlag = true;
        } else {

            MyLinkedList temp = new MyLinkedList();
            temp.prev = this;
            temp.val = this.val;
            temp.next = this.next;
            temp.numFlag = this.numFlag;

            if (this.next != null) {
                this.next.prev = temp;
            }

            this.next = temp;
            this.val = val;
        }
    }

    public void addAtTail(int val) {
        if (!numFlag) {
            this.val = val;
            this.numFlag = true;
        } else {
            MyLinkedList temp = this;
            while(temp != null) {
                if (temp.next == null){

                    temp.next =  new MyLinkedList();
                    temp.next.prev = temp;
                    temp.next.val = val;
                    temp.next.numFlag = true;

                    break;
                } else {
                    temp = temp.next;
                }
            }
        }
    }

    public void addAtIndex(int index, int val) {

        MyLinkedList temp = this;

        for (; index > 0; index--) {
            if (temp.next == null) {
                break;
            } else {
                temp = temp.next;
            }
        }

        if (index == 0) {
            MyLinkedList newList = new MyLinkedList();
            newList.val = temp.val;
            newList.numFlag = temp.numFlag;
            newList.next = temp.next;
            newList.prev = temp;

            temp.val = val;
            temp.next = newList;
        } else if (index == 1) {
            MyLinkedList newList = new MyLinkedList();
            newList.val =val;
            newList.numFlag = true;
            newList.prev = temp;

            temp.next = newList;
        }


    }

    public void deleteAtIndex(int index) {
        MyLinkedList temp = this;

        for (; index > 0; index--) {
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }

        if (temp != null) {
            if (temp.next != null) {
                temp.next.prev = temp.prev;
            } else {
                if (temp.prev != null) {
                    temp.prev.next = null;
                }
            }

            if (temp.prev != null) {
                temp.prev.next = temp.next;
            } else {
                if (temp.next != null) {
                    temp.val = temp.next.val;
                    if (temp.next.next != null) {
                        temp.next.next.prev = temp;
                    }
                    temp.next = temp.next.next;
                } else{
                    temp.val = 0;
                    temp.numFlag = false;
                    temp.next = null;
                    temp.prev=null;
                }
                
            }
        }
    }
}

Wrong Answer

• 28/65 cases passed (N/A)

Testcase

["MyLinkedList","addAtHead","addAtTail","addAtTail","addAtTail","addAtTail","addAtTail","addAtTail","deleteAtIndex","addAtHead","addAtHead","get","addAtTail","addAtHead","get","addAtTail","addAtIndex","addAtTail","addAtHead","addAtHead","addAtHead","get","addAtIndex","addAtHead","get","addAtHead","deleteAtIndex","addAtHead","addAtTail","addAtTail","addAtIndex","addAtTail","addAtHead","get","addAtTail","deleteAtIndex","addAtIndex","deleteAtIndex","addAtHead","addAtTail","addAtHead","addAtHead","addAtTail","addAtTail","get","get","addAtHead","addAtTail","addAtTail","addAtTail","addAtIndex","get","addAtHead","addAtIndex","addAtHead","addAtTail","addAtTail","addAtIndex","deleteAtIndex","addAtIndex","addAtHead","addAtHead","deleteAtIndex","addAtTail","deleteAtIndex","addAtIndex","addAtTail","addAtHead","get","addAtIndex","addAtTail","addAtHead","addAtHead","addAtHead","addAtHead","addAtHead","addAtHead","deleteAtIndex","get","get","addAtHead","get","addAtTail","addAtTail","addAtIndex","addAtIndex","addAtHead","addAtTail","addAtTail","get","addAtIndex","addAtHead","deleteAtIndex","addAtTail","get","addAtHead","get","addAtHead","deleteAtIndex","get","addAtTail","addAtTail"]
' +
  '[[],[38],[66],[61],[76],[26],[37],[8],[5],[4],[45],[4],[85],[37],[5],[93],[10,23],[21],[52],[15],[47],[12],[6,24],[64],[4],[31],[6],[40],[17],[15],[19,2],[11],[86],[17],[55],[15],[14,95],[22],[66],[95],[8],[47],[23],[39],[30],[27],[0],[99],[45],[4],[9,11],[6],[81],[18,32],[20],[13],[42],[37,91],[36],[10,37],[96],[57],[20],[89],[18],[41,5],[23],[75],[7],[25,51],[48],[46],[29],[85],[82],[6],[38],[14],[1],[12],[42],[42],[83],[13],[14,20],[17,34],[36],[58],[2],[38],[33,59],[37],[15],[64],[56],[0],[40],[92],[63],[35],[62],[32]]

Answer

[null,null,null,null,null,null,null,null,null,null,null,61,null,null,61,null,null,null,null,null,null,85,null,null,37,null,null,null,null,null,null,null,null,23,null,null,null,null,null,null,null,null,null,null,-1,23,null,null,null,null,null,31,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,8,null,null,null,null,null,null,null,null,null,6,47,null,39,null,null,null,null,null,null,null,93,null,null,null,null,83,null,93,null,null,59,null,null]

Expected Answer

[null,null,null,null,null,null,null,null,null,null,null,61,null,null,61,null,null,null,null,null,null,85,null,null,37,null,null,null,null,null,null,null,null,23,null,null,null,null,null,null,null,null,null,null,-1,95,null,null,null,null,null,31,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,8,null,null,null,null,null,null,null,null,null,6,47,null,23,null,null,null,null,null,null,null,93,null,null,null,null,48,null,93,null,null,59,null,null]

方案二

重构方案：
1、采用虚拟头，方便在头中插入数值
2、定义一个节点类，方便对其进行操作，逻辑更容易梳理

class ListNode {
    int val;
    ListNode next;

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/design-linked-list/solution/she-ji-lian-biao-by-leetcode-solution-abix/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3、类中加入一个size标签，判断是否是否超出索引，将一部分判断异常逻辑剥离出来。
4、使用单链表建立。

参考来自于：
https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E4%BB%A3%E7%A0%81
https://www.bilibili.com/video/BV1FU4y1X7WD/

class MyLinkedList {

	int size;

	ListNode listNode;

	// MyLinkedList() 初始化 MyLinkedList 对象。
	public MyLinkedList() {
		size = -1;
		listNode = new ListNode(0);

	}

	// int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
	public int get(int index) {
		if (index < 0 || index > size) {
			return  -1;
		}
		ListNode tempNode = listNode;

		while (index > 0) {
			tempNode = tempNode.next;
			index--;
		}

		return tempNode.next.val;
	}

	//void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
	public void addAtHead(int val) {
		addAtIndex(0, val);
	}

	// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
	public void addAtTail(int val) {
		addAtIndex(size + 1, val);
	}

	// void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
	public void addAtIndex(int index, int val) {
		if (index < 0 || index > (size + 1)) {
			return;
		}
		ListNode tempNode = listNode;

		while (index > 0) {
			tempNode= tempNode.next;
			index--;
		}

		ListNode addNode = new ListNode(val);

		addNode.next = tempNode.next;
		tempNode.next = addNode;

		this.size++;
	}

	// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
	public void deleteAtIndex(int index) {
		if (index < 0 || index > size) {
			return;
		}
		ListNode tempNode = listNode;

		while (index > 0) {
			tempNode = tempNode.next;
			index--;
		}
		tempNode.next = tempNode.next.next;
		this.size--;
	}

}

class ListNode {
	int val;

	ListNode next;

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

Accepted

• 65/65 cases passed (9 ms)
• Your runtime beats 87.87 % of java submissions
• Your memory usage beats 19.66 % of java submissions (43.2 MB)