一道百度算法题 LC 817 变形

简历不说了，Java多线程之类。
一道算法题，和LC的一道题有点类似：

已知一个很长很长的双向链表（不知道链表头），长度为m；输入链表的一些节点list，长度为n.  m >> n
求这个集合中的节点，在链表中有多少个相连的集合。集合即相连的节点节点片段，集合与集合不相连。

int getSetNum(List<LinkedListNode> nodes) {

}

刚开始想用并查集，后来经过提示，发现没必要，直接拿到节点，向前、向后走，标记或者直接删除访问过的节点即可。

伪代码：

1. s = set(nodes)
   
2. ans = 0
   
3. for node in nodes:
   
4.       if node in s:
   
5.             s.discard(node)
   .--
6.             pre, next = s.pre, s.next
   
7.             while pre in s:
   
8.                   s.discard(pre)
   
9.                   pre = pre.pre
   
10.             while next in s:
    
11.                   s.discard(next)
    
12.                   next = next
    
13.             ans += 1
    
14. return ans

复制代码

follow up:
如果是单链表如何解决？还是上述方法，只是需要标记当前集合最开始的头即可。

写错了，不是实习。。

这个和北美的面经题一样吗?

lifengyi 发表于 2018-12-21 15:00
这个和北美的面经题一样吗?

这个是国人面的。不过我觉得还挺有意思的。如果用并查集有点over kill了