翻转偶数长度组的节点
反转偶数长度的节点
通过额外的空间进行翻转
class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
List<Integer> nums=new ArrayList<Integer>();
ListNode cur=head;
while(cur!=null){
nums.add(cur.val);
cur=cur.next;
}
int group=1;int cnt=1;
while(cnt<=nums.size()){
if(group%2==0){
reverse(nums,cnt-group,cnt-1);
}
group++;
cnt+=group;
}
cnt-=group;
if((nums.size()-cnt)%2==0){
reverse(nums,cnt,nums.size()-1);
}
cur=head;
int index=0;
while(cur!=null){
cur.val=nums.get(index++);
cur=cur.next;
}
return head;
}
public void reverse(List<Integer> nums,int start,int end){
int i=start;int j=end;
while(i<j){
int t=nums.get(i);
nums.set(i,nums.get(j));
nums.set(j,t);
i++;j--;
}
}
}
对于分组group cnt当前分组对应的总共节点数
int group=1;int cnt=1;
while(cnt<=nums.size()){
if(group%2==0){
reverse(nums,cnt-gourp,cnt-1);//总共元素个数为group
}
group++;
cnt+=group;
}
//对于剩下的元素个数
cnt-=group;
if((nums.size()-cnt)%2==0){
reverse(nums,cnt,nums.size()-1);//cnt-1是倒数第二组的最后一个节点,cnt是当前组的第一个节点
}
k个一组进行翻转
两两交换链表中的节点
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(-1,head);
for(ListNode cur=dummy;cur.next!=null&&cur.next.next!=null;){
ListNode p=cur.next;ListNode q=cur.next.next;
cur.next=q;
p.next=q.next;
q.next=p;
cur=p;
}
return dummy.next;
}
}