通过hashMap维护前缀和,类似区间和为0最长区间
链表区间和 通过Map[HTML_REMOVED] 可以快速定位链表节点
从链表删除区间和为0的连续节点
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
//通过sum维护前缀和
int sum=0;
ListNode dummy=new ListNode(-1,head);
ListNode p=head;
Map<Integer,ListNode> map=new HashMap<Integer,ListNode>();
map.put(0,dummy);//将前缀和为0的所有的节点先删除
while(p!=null){
sum+=p.val;
if(map.containsKey(sum)){
ListNode node=map.get(sum);
ListNode del=node.next;
node.next=p.next;
//将删除的节点所有的map删除
int dsum=sum;
while(del!=p){
dsum+=del.val;
map.remove(dsum);
del=del.next;
}
}else{
//将当前前缀和加入map
map.put(sum,p);
}
p=p.next;
}
return dummy.next;
}
}
链表组件
链表组件
判断链表最多有多少段在集合nums中出现
class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> set=new HashSet<>();
set.add(nums[i]);
}
for(int i=0;i<nums.length;i++){
int res=0;int s=0;
for(ListNode p=head;p!=null;p=p.next){
if(set.contains(p.val)){
s++;
}else{
if(s>0){
res++;
s=0;
}
}
}
if(s>0){
res++;
}
return res;
}
}
交换链表的两个节点
方式一:直接交换两个结点的值
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode dummy=new ListNode(0,head);
ListNode p=head;
for(int i=0;i<k-1;i++){
p=p.next;
}
ListNode r=head;
for(int i=0;i<k-1;i++){
r=r.next;
}
ListNode q=head;
while(r.next!=null){
q=q.next;
r=r.next;
}
int t=p.val;
p.val=q.val;
q.val=t;
return dummy.next;
}
}
方式二:通过交换对应的节点
class Solution {
public ListNode swapNodes(ListNode head, int k) {
int n=0;
ListNode cur=head;
while(cur!=null){
n++;
cur=cur.next;
}
if(k>n/2){
k=n-k+1;
}
System.out.println("k"+k);
//找到正数和倒数第k个节点的前一个结点
ListNode dummy=new ListNode(0,head);
ListNode p=dummy;
for(int i=0;i<k-1;i++){
p=p.next;
}
ListNode r=dummy;
for(int i=0;i<k;i++){
r=r.next;
}
ListNode q=dummy;
while(r!=null&&r.next!=null){
q=q.next;
r=r.next;
}
System.out.println("p.val="+p.val+"q.val"+q.val);
if(p.next==q){
ListNode tmp=q.next;
q.next=tmp.next;
p.next=tmp;
tmp.next=q;
return dummy.next;
}
System.out.println("p.val="+p.val+"q.val"+q.val);
if(p==q){//如果需要交换的是同一个节点,不需要交换,直接返回
return dummy.next;
}
ListNode t=p.next.next;
ListNode s=q.next.next;
//需要交换的节点
ListNode op0=p.next;
ListNode op1=q.next;
op0.next=null;op1.next=null;
p.next=null;q.next=null;
p.next=op1;
op1.next=t;
q.next=op0;
op0.next=s;
return dummy.next;
}
}
对于交换链表中的两个节点
ListNode p,q;//p,q分别指向需要交换的节点的前驱节点
ListNode t=q.next;
q.next=t.next;
p.next=t;
t.next=q;