LeetCode 203. 移除链表元素

Scroll Down

LeetCode 203. 移除链表元素

题目:

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

示例:

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

示例:

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

哨兵节点法

哨兵结点是最简单的办法了,直接用一个哨兵结点,然后遍历如果值不等于对应值就接在哨兵结点后面,最后返回一个新的链表.

 public ListNode removeElements(ListNode head, int val) {
        ListNode tempHead = new ListNode(0);
        ListNode dummnyNode = tempHead;
        while(head != null){
            if(head.val != val){
                tempHead.next = new ListNode(head.val);
                tempHead = tempHead.next;
            }
            head = head.next;
        }
        return dummnyNode.next;
    }

迭代法

因为知道删除结点时只需要将head.next = head.next.next;即可删除head.next结点,但是要考虑的是如果删除的是头结点,删除头结点之后如果链表为空的特殊场景,考虑到这两个特殊场景后,就可以直接遍历链表了

public ListNode removeElements2(ListNode head, int val) {
       //判断是否删除头结点
        while (head != null && head.val == val) {
            head = head.next;
        }
        //判空
        if (head == null) {
            return null;
        }
        ListNode finalHead = head;
        while (head.next != null) {
            if (head.next.val == val) {
                head.next = head.next.next;
            }else {
                head = head.next;
            }
        }
        return finalHead;
    }