链表与递归

LeetCode第203题

题目：

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

1.不使用虚拟头节点
public class Solution {    public ListNode removeElements(ListNode head, int val) {        // 链表不为空，并且头节点就是要删除的元素        while (head != null && head.val == val) {            ListNode delNode = head;            head = head.next;            delNode.next = null;        }        if (head == null) {             // 所有元素都是要删除的元素，并且在上面已经删完            return head;        } else {             // 现在的链表头节点不是要删除的元素            ListNode prev = head;            while (prev.next != null) {                if (prev.next.val == val) { // 删除                    ListNode delNode = prev.next;                    prev.next = delNode.next;                    delNode.next = null;                } else { // 不删除                    prev = prev.next;                }            }            return head;        }    }}

2.使用虚拟头节点

public class Solution2 {

public ListNode removeElements(ListNode head, int val) {    // 虚拟头节点    ListNode dummyHead = new ListNode(0);    dummyHead.next = head;    ListNode prev = dummyHead;    while (prev.next != null) {        if (prev.next.val == val) {            ListNode delNode = prev.next;            prev.next = delNode.next;            delNode.next = null;        } else {            prev = prev.next;        }    }    return dummyHead.next;}

}

3.递归
public class Solution3 {    public ListNode removeElements(ListNode head, int val) {        if (head == null) {            return head;        }        head.next = removeElements(head.next, val);        return head.val == val ? head.next : head;    }}

原文地址：