如何打开网页_程序开发总结_seo推广专员_知名seo公司

题目内容

题目分析

• 添加哨兵节点dummy。
• 在第n个节点前插入节点时，应该找到第n - 1个节点（即前一个节点），才能完成插入操作。
• 在删除第n个节点时，应该找到第n - 1个节点（即前一个节点），才能完成删除操作。

(1) 获取第n个节点的值

• cur指向头节点（第0个节点是头节点），cur向后移动n次后，指向第n个节点。

MyLinkedList.prototype.get = function(index) {if(index < 0 || index > this.size - 1){return -1;}var cur = this.dummy.next;while(index){cur = cur.next;index--;}return cur.val;
};

(2) 头部插入节点

• 新建待插入节点headNode。
• ① headNode节点指向头节点。
• ② 哨兵节点指向headNode节点。
• 链表长度+1。

MyLinkedList.prototype.addAtHead = function(val) {var headNode = new ListNode(val);headNode.next = this.dummy.next;this.dummy.next = headNode;this.size++;
};

(3) 尾部插入节点

• 新建待插入节点tailNode，新建节点自动指向null。
• cur指向哨兵节点，cur一直向后移动，直到找到尾节点。
• ① 原尾节点指向tailNode节点，tailNode节点成为新尾节点。
• 链表长度+1。

MyLinkedList.prototype.addAtTail = function(val) {var tailNode = new ListNode(val);var cur = this.dummy;while(cur.next != null){cur = cur.next;}cur.next = tailNode;this.size++;
};

(4) 第n个节点前插入节点

• 新建待插入节点newNode。
• cur指向哨兵节点，cur向后移动n次后，指向第n - 1个节点。
• ① newNode节点指向第n个节点。
• ② 第n - 1个节点指向newNode节点。
• 链表长度+1。

MyLinkedList.prototype.addAtIndex = function(index, val) {if(index < 0 || index > this.size){return;}var newNode = new ListNode(val);var cur = this.dummy;while(index){cur = cur.next;index--;}newNode.next = cur.next;cur.next = newNode;this.size++;
};

(5) 删除第n个节点

• cur指向哨兵节点，cur向后移动n次后，指向第n - 1个节点。
• ① 第n - 1个节点指向第n + 1个节点（第n个节点的下一个节点）。
• 链表长度-1。

MyLinkedList.prototype.deleteAtIndex = function(index) {if(index < 0 || index > this.size - 1) {return;}var cur = this.dummy;while(index){cur = cur.next;index--;}cur.next = cur.next.next;this.size--;    
};

完整代码

function ListNode(val, next) {this.val = (val===undefined ? 0 : val);this.next = (next===undefined ? null : next);
}var MyLinkedList = function() {this.size = 0;this.dummy = new ListNode();
};/** * @param {number} index* @return {number}*/
MyLinkedList.prototype.get = function(index) {if(index < 0 || index > this.size - 1){return -1;}var cur = this.dummy.next;while(index){cur = cur.next;index--;}return cur.val;
};/** * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtHead = function(val) {var headNode = new ListNode(val);headNode.next = this.dummy.next;this.dummy.next = headNode;this.size++;
};/** * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtTail = function(val) {var tailNode = new ListNode(val);var cur = this.dummy;while(cur.next != null){cur = cur.next;}cur.next = tailNode;this.size++;
};/** * @param {number} index * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtIndex = function(index, val) {if(index < 0 || index > this.size){return;}var newNode = new ListNode(val);var cur = this.dummy;while(index){cur = cur.next;index--;}newNode.next = cur.next;cur.next = newNode;this.size++;
};/** * @param {number} index* @return {void}*/
MyLinkedList.prototype.deleteAtIndex = function(index) {if(index < 0 || index > this.size - 1) {return;}var cur = this.dummy;while(index){cur = cur.next;index--;}cur.next = cur.next.next;this.size--;    
};/*** Your MyLinkedList object will be instantiated and called as such:* var obj = new MyLinkedList()* var param_1 = obj.get(index)* obj.addAtHead(val)* obj.addAtTail(val)* obj.addAtIndex(index,val)* obj.deleteAtIndex(index)*/