两两交换链表中的节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路： 首先将整个链表倒置，然后再在倒置后的链表上以两个节点为单位再进行一次倒置。但是这种思路只适用与偶数个节点，如果是奇数个节点，最后一个节点倒置之后，再在倒置后的链表中以两个节点为单位进行倒置会打乱最终的顺序。所以在对链表进行操作之前，首先判断节点个数是否为奇数个。如果是奇数个，那么就将最后一个节点取下保存地址，之后操作完成后，再将该节点拼接到最终链表中。
代码：
class Solution {
public ListNode swapPairs(ListNode head) {
int len=0;
ListNode cur=head,end;
ListNode temp=new ListNode();
//链表为空或者只有一个节点直接返回
if(head==null) {
return head;
}
if(head.next==null) {
return head;
}
//遍历获得链表长度并保存最后一个节点的前一个节点地址
while(cur.next.next!=null) {
len++;
cur=cur.next;
}
//判断节点数是否为奇数个
if((len+2)%2!=0) {
//奇数个切断最后一个节点并保存地址以便之后拼接
end=cur.next;
cur.next=null;
} else {
end=null;
}
//倒置整个链表
head=reverse(head);
//记录最终链表尾巴位置方便之后拼接
ListNode tail=head.next;
//以两个节点为单位倒置头插
while(head!=null) {
ListNode hNext=head.next.next;
ListNode headNext=head.next;
headNext.next=temp.next;
temp.next=head;
head=hNext;
}
//拼接
tail.next=end;
return temp.next;
}
//链表倒置
public ListNode reverse(ListNode head) {
ListNode temp=new ListNode();
while ( head != null ) {
ListNode headNext=head.next;
head.next=temp.next;
temp.next=head;
head=headNext;
}
return temp.next;
}
}
K 个一组翻转链表
题目描述：
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
思路： 看到这题我就想到我前面的两两交换链表节点的做法。首先遍历链表记录长度，判断长度与k是否为整数倍关系，如果不是就要进行取模运算得到余数，并通过findNode函数得到倒数余数个点的地址以及倒数余数加一个点的地址，从倒数余数个点处断开链表，之后完成操作后再拼接。反转断开后的链表，并按照k个一组的方式来进行头插，在头插之前会先定义一个头节点来方便后续插入。在之后的循环中，head用来记录每一个k组的第一个元素地址，nextPre来记录每一个k组的最后一个元素的地址，Next来记录下一个k组的第一个元素的地址，nextPre和Next都通过cur接收head地址值之后遍历k-1次获取，然后头插的操作相当于再次逆置链表，只不过是以k个元素为一组的。完成外部循环后，链表拼接上之前断开的一部分即可。这种方法虽然能运行成功，但是效率比较低，代码冗长，自己钻牛角尖写出来的。
代码：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null) {
return null;
}
ListNode cur=head;
int len=0;
//得到链表长度
while(cur!=null) {
cur=cur.next;
len++;
}
//链表长度等于k直接逆置返回
if(len==k) {
return reverse(head);
}
ListNode endPre;
ListNode end;
//链表长度不等于k的倍数
if(len%k!=0) {
//记录倒数第k+1个节点位置，方便之后断开操作
endPre=findNode(head,len%k+1);
//记录倒数第k个节点位置
end=findNode(head,len%k);
//断开后面的节点
endPre.next=null;
} else {
//链表长度是k的倍数，则不需要断开
end=null;
endPre=null;
}
//反转剩余的链表
head=reverse(head);
//记录反转后头的位置，在最终链表中改位置为最后一个k组的第一个元素位置
ListNode tail=head;
int count=k-1;
while(count!=0) {
//通过遍历得到最终返回链表的最后一个k组的最后一个元素的地址
tail=tail.next;
count--;
}
ListNode temp=new ListNode(-1);
ListNode Next=null;
ListNode nextPre=null;
cur=head;
int tmp=0;
while(head!=null) {
tmp=k-1;
while(tmp!=0) {
cur=cur.next;
tmp=tmp-1;
}
//通过循环得到上一个k组最后一个元素地址
nextPre=cur;
//这一个k组的第一个元素地址
Next=cur.next;
//头插操作
nextPre.next=temp.next;
temp.next=head;
//更新
head=Next;
cur=Next;
}
//通过之前记录的最后一个k组的最后一个元素的地址完成拼接
tail.next=end;
return temp.next;
}
//逆置链表
public ListNode reverse(ListNode head) {
ListNode temp=new ListNode(-1);
while(head!=null) {
ListNode headNext=head.next;
head.next=temp.next;
temp.next=head;
head=headNext;
}
return temp.next;
}
//找出倒数第k个节点
public ListNode findNode(ListNode head,int k) {
if(head==null) {
return null;
}
ListNode fast=head;
ListNode slow=head;
while(k!=1) {
fast=fast.next;
k=k-1;
}
while(fast.next!=null) {
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
