203.移除链表元素
学习链接
个人思路
循环遍历完整链表，遇到
next.value === target 时， next = next.next，设置一个dummy虚拟头方便后续操作为什么要设置dummy虚拟头：如果第一个头节点 head.val === val时，不好删除操作，所以设置一个虚拟头方便后续处理
解题代码
/** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { const dummy = new ListNode(0, head); let cur = dummy while(cur.next){ if(cur.next.val === val){ cur.next = cur.next.next continue } cur = cur.next } return dummy.next };
707.设计链表
学习链接
个人思路
这道理还是涉及到了链表常用的添加、删除操作，还是使用dummy节点方便处理
解题代码
function ListNode (val){ this.val = val this.next = null } var MyLinkedList = function() { this.head = null this.size = 0 }; /** * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function(index) { if(index < 0 || index > this.size -1){ return -1 } let step = index let cur = this.head while(step){ cur = cur.next step -- } return cur.val }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function(val) { const node = new ListNode(val) node.next = this.head this.head = node this.size ++ }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function(val) { if(this.head === null){ this.addAtHead(val) } else{ const node = new ListNode(val) let cur = this.head while(cur.next){ cur = cur.next } cur.next = node this.size ++ } }; /** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if(index <= 0){ this.addAtHead(val) } else if(index === this.size){ this.addAtTail(val) } else if(index > this.size-1){ // 注意这里第一次写错了 return null } else{ let cur = this.head let step = index while(step > 1){ cur = cur.next step -- } const node = new ListNode(val) node.next = cur.next cur.next = node this.size ++ } }; /** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { if(index < 0 || index > this.size - 1){// 注意这里第一次写错了 return null } else{ const dummy = new ListNode(null) dummy.next = this.head let cur = dummy let step = index while(step){ cur = cur.next step -- } if(index === 0){ this.head = cur.next.next } cur.next = cur.next.next this.size -- } };
206.反转链表
学习链接
个人想法
比较复杂，需要一直把cur.next 指向cur.prev，所以需要双指针来一直记住cur和cur.next的位置
解题代码
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let pre = null let cur = head let node = null // 临时保存节点 while(cur){ node = cur.next // 记录cur.next cur.next = pre // 修改指向 pre = cur // pre移到下一位 cur = node // cur移到下一位 } return pre };