每天进步一点点🤏

移除链表元素

  • 1476 字

移除链表元素

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给你一个链表的头节点 head 和一个整数 val,请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
思路:
先确定头节点,遍历链表,如果头节点的val值与指定的val值相同,跳到下一个节点,
接下来是遍历剩下的节点,创建不等于val值的新节点,插入链表中,直至节点遍历完成

代码:
class ListNode
{
    public $val = 0;
    /**
     * @var ListNode|null
     */
    public $next = null;

    function __construct($val = 0, $next = null)
    {
        $this->val  = $val;
        $this->next = $next;
    }
}

function removeElements($head, $val)
{
    // 创建一个新的链表存储符合条件的节点
    $node = new ListNode(null);

    // 确定头节点开始的位置
    while ($head) {
        if ($head->val != $val) {
            $node->val = $head->val;
            break;
        }

        $head = $head->next;
    }

    // 遍历剩下的节点, 将符合条件的节点存入链表中
    $this->cycle($node, $head->next, $val);

    return $node;
}

private function cycle($all, $node, $val)
{
    if (!$node) {
        return;
    }

    if ($node->val == $val) {
        // 如果符合条件, 继续遍历下一个节点
        $this->cycle($all, $node->next, $val);
    } else {
        // 如果不符合条件, 创建一个值一样的节点存储到链表的下一个位置
        $all->next = new ListNode($node->val);

        // 链表位置向后移动一位
        $this->cycle($all->next, $node->next, $val);
    }
}