b2b商城网站方案国际新闻最新消息今天

leetcode203

什么是链表

之前不懂链表的数据结构，一看到链表的题目就看不明白
链表是通过next指针来将每个节点连接起来的，题目中给的链表是单向链表，有两个值，一个val表示值，一个next：表示连接的下一个节点
对于题目中给出的head = [1,2,6,3,4,5,6]，实际的结构是这样的：

const node6 = { val: 6, next: null }
const node5 = { val: 5, next: node6 }
const node4 = { val: 4, next: node5 }
const node3 = { val: 3, next: node4 }
const node2 = { val: 6, next: node3 }
const node1 = { val: 2, next: node2 }
const nodeList = { val: 1, next: node1 }

nodeList是头节点，然后通过next连接下一个节点，一直到next:null。
单向链表都只能向下查询，如果是双向链表的话会多一个prev属性，指向前一个节点

方法1

题目中的意思是，如果找到一个节点的val == target，那么就要删除这个节点。
关于删除节点，如果需要删除的节点在头节点，我们需要把头节点往下移动，通过改变头节点的方式来删除。
例如：head = [1,1,2,3],val = 1
那么我们让head = head.next来修改head的头节点，就可以删除头节点。
如果需要删除掉节点在中间，像下面图片中一样，原本cur.next -> 6，我们需要跳过这一项，那么就让cur.next = cur.next.next，就跳过了中间项，这样的话新的节点就是1->2->3

var removeElements = function (head, val) {if(!head){return head;}// 头节点是目标删除节点while(head && head.val === val){head = head.next;}let cur = head;while(cur){while(cur.next && cur.next.val === val){cur.next = cur.next.next;}cur = cur.next;}return head;
}

方法2

前面方法1中针对头节点和非头节点的删除方式其实是不同的，那么有没有什么方式可以让头节点和非头节点都用相同的方式来进行删除呢？
我们可以考虑创建一个**虚拟头节点dummy**，让dummy.next = head 这样的话，需要删除掉所有节点都是属于中间节点，都以删除中间节点的方式来进行删除操作即可
需要注意的是，最终返回的是dummy.next，因为dummy是我们创建出来的虚拟节点，实际是不存在的，真正的头节点是dummy.next

var removeElements = function (head, val) {if (!head) {return head;}let dummy = { val: 0, next: head };let cur = dummy;while (cur) {while (cur.next && cur.next.val === val) {cur.next = cur.next.next;}cur = cur.next;}return dummy.next;
}