817. 链表组件

痛定思痛。 2023-02-20 13:53 7阅读 0赞

# 题目来源 #

[817. 链表组件][817.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

看懂题目是关键，因为缺失的结点值会将原链表断开，实际上就是让我们求有多少个相连的子链表。

## 栈 ##

方法1：遍历链表，每个节点在G中找到则为1，否则为0，存入栈中stack\[1,1,0,1,1\]，然后再对栈进行判断:

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    public int numComponents(ListNode head, int[] G) {
        
            Set<Integer>  set = new HashSet<>();
            for (int i :G ) {
        
                set.add(i);
            }
    
            Stack<Integer> stack = new Stack<>();
            while (head != null){
        
                if (set.contains(head.val)){
        
                    stack.push(1);
                }else{
        
                    stack.push(0);
                }
                head = head.next;
            }
            
            boolean isChange = true;
            int ans = 0;
            while (!stack.empty()){
        
                int i = stack.pop();
                if (i == 1 && isChange){
        
                    ans++;
                    isChange = false;
                }
                
                if (i == 0){
        
                    isChange = true;
                }
            }
            
            return ans;
        }
    }

![在这里插入图片描述][20200627215156887.png]

## 线性扫描 ##

我们对链表进行一次扫描，一个组件在链表中对应一段极长的连续节点，因此如果当前的节点在列表 G 中，并且下一个节点不在列表 G 中，我们就找到了一个组件的尾节点，可以将答案加 1。

例如，当链表为 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，G 为 \[0, 2, 3, 5, 7\] 时，我们扫描之后可以发现 0, 3, 5, 7 四个节点是组件的尾节点，那么答案就为 4。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int numComponents(ListNode head, int[] G) {
        
            Set<Integer>  set = new HashSet<>();
            for (int i :G ) {
        
                set.add(i);
            }
    
            int ans = 0;
            while (head != null){
        
                // 当前节点是子链表的尾节点：下一个节点是null或者下一个节点不在set中
               if (set.contains(head.val) && (head.next == null || !set.contains(head.next.val))){
        
                   ans++;
               }
    
               head = head.next;
            }
    
            return ans;
        }
    
    }

![在这里插入图片描述][20200627215249334.png]

[817.]: https://leetcode-cn.com/problems/linked-list-components/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627215335823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200627215156887.png]: https://img-blog.csdnimg.cn/20200627215156887.png
[20200627215249334.png]: https://img-blog.csdnimg.cn/20200627215249334.png