No.203 移除链表元素
题目
删除链表中等于给定值 val 的所有节点。
测试用例:
- 输入: 1->2->6->3->4->5->6, val = 6 ;输出: 1->2->3->4->5
- 输入: 1->1,val = 1 ; 输出: null
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
};
思路
想到的是进行遍历判断，如果节点的 val 值与方法的第二个参数相同，就将此节点的 next 的值赋值给上一节点的 next 属性，从而替换当前节点，达到目的。但是在链表中，我们没有办法获取到当前节点的上一节点。问题就陷入了死胡同，咋整呢？
我们可以为传入的链表增加一个链表头。然后判断当前节点的 next 属性的 val 是否与传入的相同。
第一遍解答
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
if(head === null) return null
let tmp = new ListNode(-1)
tmp.next = head
let iteratorTmp = tmp
while(iteratorTmp.next !== null) {
if(iteratorTmp.next.val == val) {
iteratorTmp.next = iteratorTmp.next.next
} else {
iteratorTmp = iteratorTmp.next;
}
}
return tmp.next
};
解析
如上述说的那样，我们增加了一个指向新链表的指针。通过遍历这个指针，达到改变链表的目的。当当前节点的 next 的 val 值与第二个参数相同时，就执行赋值操作。
进阶解答
var removeElements = function(head, val) {
if (!head) {
return null;
}
head.next = removeElements(head.next, val);
if (head.val === val) {
return head.next;
} else {
return head;
}
};
很明显的，递归解法。这有点儿像我们刚开始想的那样，遍历链表，然后使用节点的 next 属性替换当前节点。
想法
做了有几道关于链表的题目，发现链表的一些题目比较适合用递归的方式来解决。