算法——移除链表元素(leetcode203)
移除链表元素首先我们要理解链表这种数据结构,它跟数组不一样它可以分布在内存中的各个位置链表节点由值和指针组成,指针指向下一个链表节点。
移除链表元素简而言之就是将符合条件的链表节点给移除出去我们不能直接将其移除而是通过将被移除节点的上一个节点的指针指向被移除节点的下一个节点的地址就完成了链表元素的移除操作特别要注意的是java中是有内存回收机制的所以不需要手动释放节点而c++是需要的。
方法一(单独处理头结点)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {//处理头结点while(head!=null&&head.val==val){head=head.next;}ListNode cur=head;while(cur!=null&&cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}
}
方法二(创建一个虚拟节点next指针指向头结点)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {//定义一个虚拟节点ListNode vNode=new ListNode();vNode.next=head;ListNode cur=vNode;while(cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;}else{cur=cur.next;}}return vNode.next;}
}